In this lesson (tutorial), problems in which a result comprises a sequence of steps or choices (at different stages of the problem solving) that have to be made in order to achieve the optimal solution, are considered. Greedy programming is a method by which a solution is determined based on making the locally optimal (performance) choice at any given moment. In other words, the best decision is chosen, from the viewpoint of the current stage of the solution. 

Depending on the problem, the greedy method of solving a task may or may not be the best approach. If it is not the best approach, then it often returns a result which is approximately correct but sub-optimal. In such cases dynamic programming or brute-force can be the optimal approach. On the other hand, if it works correctly, its running time is usually faster than those of dynamic programming or brute-force.

The Coin Changing Problem

Example

Imagine that you have too many coins of value 1; too many coins of value 2, and too many coins of value 5. Coin values such as one, two and five are called denominations. 

Assume that you are asked to pay a value of 6 (dollars) for an article, from among the coins, 1, 2 and 5. Remember, there are too many 1 coins, too many 2 coins and too many 5 coins. 6 can be paid with 2 + 2 + 2 = 6, making the number of coins 3. It can be paid with 2 + 2 + 1 + 1 = 6, making the number of coins 4. It can be paid with 1 + 1 + 1 + 1 + 1 + 1 = 6, making the number of coins, 6. It can just be paid with 5 + 1 = 6, making the number of coins 2.

Remember, you have too many coins of value 1, too many coins of value 2, and too many coins of value 5. From above, 6 can be paid with 2 coins. It can also be paid with 3 coins; it can also be paid with 4 coins; it can also be paid with 6 coins. The smallest number of coins that 6 can be paid with is 2, for the values: 5 and 1. 

The coin changing problem is to find the minimum number of coins with which a given amount of money can be paid. The minimum number above is 2. The problem can be approached by a greedy algorithm that always selects the largest denomination not exceeding the remaining amount of money to be paid. As long as the remaining amount is greater than zero, the process is repeated (by choosing next bigger down, and next bigger down). In that way, few number of coins are obtained.

For the above example, start with 5. The next smaller denomination given is 2. If 2 is added to 5, it will be 7, above 6. So 2 cannot be chosen next. The next and last option is the denomination, 1. If 1 is added to 5, the required amount of 6 would be obtained. So 1 is chosen. The denominations chosen are 5 and 1, making a minimum of 2 coins altogether.

Note: The objective of the coin changing problem is to find the smallest number of coins that sum up to the paid amount.

The Coin Changing Problem Question

You are given n denominations 0 < m₀ <= m₁ <= . . . <= m_n−1 . Find the minimum number of coins to pay the amount, k. These denominations are put in an array from smallest to biggest. Assume the number of each denomination is infinite. 

Solution

For the above example, 6 ÷ 5 = 1 remainder 1. The divisor, 5 is chosen as the first denomination. From the quotient, the whole number 1 is the number of the denominations of 5, to be used. From the quotient, the amount which is the remainder, to add to 5 to make 6 is 1, and so the remaining amount from 6 to be divided, is 1. Three denominations were given: 1, 2 and 5. So, denomination 2 has to be skipped (coming downwards), for division of the remaining amount of 1 to be considered. 1 divided by 1 is 1 remainder 0. The divisor, 1 is chosen as the next denomination. From the quotient, the whole number 1 is the number of the denominations of 1, to be used. Six is not among the denominations. From the new quotient, the amount which is the remainder, to add to 5+1 = 6, in order to make 6, is 0. The algorithm ends. Zero is not a denomination.

To generalize, the amount to be paid is divided by the highest denomination, to have the whole number and remainder. The whole number becomes the number of coins for that denomination and the remainder is what has to be divided next, by the next possible lower denomination. This repeats downwards, until the remainder is zero. 

Greedy Algorithm Coding for Coin Changing Problem

The denominations are put in an array from smallest to biggest. The iteration (dividing) has to be done from the end of the array to the beginning of the array. The amount to be paid next is k, from the total amount given, which is still k (see code below). The output in the following code is a two dimensional array, where the first column is for the denomination and second column is for the number of coins for that denomination. The greedy algorithm function in JavaScript, for the Coin Changing Problem, is in the following program:

<script type='text/javascript'>
    "use strict";

    function greedyCoinChanging(M, k) {
        let n = M.length;   
        let result = [];

        for (let i=n-1; i>=0; i--) {
            if (M[i] > k)    //the next denomination down, is higher than the next amount needed, e.g. 2>1 above
                continue;
            let wholeNo = parseInt(k / M[i]);    //integer division beginning with the total amount to be paid
            result.push([M[i], wholeNo]);
            k = k % M[i];
        }

        return result;
    }

    const v = [1, 2, 5];
    let result = greedyCoinChanging(v, 6);
    let noCoins = 0;
    for (let i=0; i<result.length; i++) {
        document.write(result[i][0] + ' => ' + result[i][1] + '<br>');
        noCoins = noCoins + result[i][1];
    }
    document.write('<br>');
        
    document.write("Number of coins: " + noCoins + '<br>');

</script>

The output is:

5 => 1
1 => 1

Number of coins: 2

    Number of coins: 2 

which means,

Number of coins is 2, which is the size (length) of the map.

Time Complexity

The function returns the list of pairs: denomination/number of coins. The time complexity of the above algorithm is O(n). 

Example of Sub-optimal Result by Greedy Algorithm

Consider the situation, where a total amount of 6 is to be paid, and the denominations this time are 1, 3, and 4. Remember that the number of coins for each denomination provided is countless.

By greedy algorithm, 6 is divided by 4 to give the quotient, 1 remainder 2. The number of coins for 4 is 1. The next denomination, downwards, is 3 and the remainder of the previous division, 2 cannot divide 3 to give a whole number and any possible remainder. Next the remainder, 2 is divided by 1 to give 2 remainder 0. With remainder 0, the algorithm is ended. The number of coins for the denomination 1 is 2. The sub-optimal result with these 3 coins is:

 with 3 coins altogether. The correct or optimal result is:

with 2 coins altogether. 

The total number of coins here is 2, which is less than 3 coins above. So greedy algorithm is not optimal all the time. Dynamic Programming taught in the next lesson (tutorial) will always give an optimal result.

It turns out that the greedy algorithm is optimal (correct) for only some denomination selections, but not for all.