Classic example of an optimization problem: Use the minimum number of coins to find zero.

Suppose a 24-hour vending machine in a beautiful neighborhood uses the minimum number of coins for each cash transaction (mobile payment is not currently supported) to reduce the number of coin replenishment and save costs.

For example, Zhang SAN used a one-yuan note (1 yuan =100 cents) to buy a total of 37 cents worth of pickled mustard, tea eggs and fat zai Happy water. Assuming that the coins have a face value of 1 cent, 5 cent, 10 cent and 25 cent, how many coins should he retrieve?

The answer is six: two for 25 cents, one for 10 cents, and three for 1 cent.

How do you calculate that?

Start with the coin with the largest face value (25 cents) and use as many coins as you can, then use as many coins as you can with the second largest face value. This approach is called greedy algorithms — trying to solve a problem at its maximum.

The code for using the minimum number of coins to find zero under Golang’s greedy algorithm is as follows:

package main

import (
	"fmt"
        "sort"
)

func minCoinsGreed(coinValus []int, change int) int {
	// Use the minimum number of coins to find zero: greedy algorithm
	// Start with the largest coin (25 cents) and use as many coins as you can,
	// Then use the second largest coin as many times as possible.
	// Make sure the coins are sorted in descending order
	sort.Sort(sort.Reverse(sort.IntSlice(coinValus)))
	coins := 0
	for _, va := range coinValus {
		// The quotient indicates the number of coins that can be used in this denomination
		div := change / va
		// Total number of coins
		coins += div
		// The remainder is the denomination that still needs change
		change = change % va
		// Exit the loop early if the change has been made
		if change == 0 {
			break}}return coins

}

func main(a) {
	coinValues := []int{25.10.5.1}
	fmt.Println("Number of coins required:", minCoinsGreed(coinValues, 63))
	// Number of coins required: 6
	coinValus = []int{25.21.10.5.1}
	fmt.Println("Number of coins required:", minCoinsGreed(coinValues, 63))
	// Number of coins required: 6
}
Copy the code

If there were 21 cents in the change, the greedy algorithm would result in six. The actual minimum number of coins should be 3 21 cent coins. Therefore, the greedy algorithm may not get the optimal solution in calculating the minimum number of coins.

To ensure that the optimal solution is found, the next article will attempt to solve coin change elegantly recursively.