Finding the minimum set of coins that make a given value-CodePudding

I've been trying to figure out if there would be a way to get the optimal minimum set of coins that would be used to make the change.

The greedy algorithm approach for this has an issue such as if we have the set of coins {1, 5, 6, 9} and we wanted to get the value 11. The greedy algorithm would give us {9,1,1} however the most optimal solution would be {5, 6}

From reading through this site I've found that this method can give us the total minimum number of coins needed. Would there be a way to get the set of coins from that as well?

CodePudding user response：

I'm assuming you already know the Dynamic Programming method to find only the minimum number of coins needed. Let's say that you want to find the minimum number of coins to create a total value K. Then, your code could be

vector <int> min_coins(K   1);
min_coins[0] = 0; // base case
for(int k = 1; k <= K;   k) {
    min_coins[k] = INF;
    for(int c : coins) { // coins[] contains all values of coins
        if(k - c >= 0) {
            min_coins[k] = min(min_coins[k], min_coins[k - c]   1);
        }
    }
}

Answer to your question: In order to find the actual set of coins that is minimal in size, we can simply keep another array last_coin[] where last_coin[k] is equal to the coin that was last added to the optimal set of coins for a sum of k. To illustrate this:

vector <int> min_coins(K   1), last_coin(K   1);
min_coins[0] = 0; // base case
for(int k = 1; k <= K;   k) {
    min_coins[k] = INF;
    for(int c : coins) {
        if(k - c >= 0) {
            if(min_coins[k - c]   1 < min_coins[k]) {
                min_coins[k] = min_coins[k - c]   1;
                last_coin[k] = c; // !!!
            }
        }
    }
}

How does this let you find the set of coins? Let's say we wanted to find the best set of coins that sum to K. Then, we know that last_coin[K] holds one of the coins in the set, so we can add last_coin[K] to the set. After that, we subtract last_coin[K] from K and repeat until K = 0. Clearly, this will construct a (not necessarily the) min-size set of coins that sums to K.

Possible implementation:

int value_left = K;
while(value_left > 0) {
    last_coin[value_left] is added to the set
    value_left -= last_coin[value_left]
}