找到给定值的最小硬币集

Question

我一直在试图弄清楚是否有办法获得用于进行找零的最佳最小硬币集。

这种贪心算法方法有一个问题，例如如果我们有一组硬币 {1, 5, 6, 9} 并且我们想得到值 11。贪心算法会给我们 {9, 1,1} 但是最佳解决方案是 {5, 6}

通读此 site 我发现此方法可以为我们提供所需的最少硬币总数。是否也有办法从中获取一组硬币？

Answer 1

我假设您已经知道动态规划方法只找到所需的最小数量硬币。比方说，你想找到最少数量的硬币来创造一个总价值 K。那么，您的代码可能是

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);
        }
    }
}

回答你的问题：为了找到实际的组最小的硬币，我们可以简单地保留另一个数组 last_coin[] 其中 last_coin[k]等于最后加入最优硬币集合的硬币总和为k。为了说明这一点：

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; // !!!
            }
        }
    }
}

这如何让您找到硬币组？假设我们想找到总和为 K 的最佳硬币组。然后，我们知道 last_coin[K] 持有集合中的一个硬币，因此我们可以将 last_coin[K] 添加到集合中。之后，我们从 K 中减去 last_coin[K] 并重复直到 K = 0。显然，这将构建一个（不一定 the）最小大小的硬币集合，总和为 K.

可能的实现：

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

找到给定值的最小硬币集

Finding the minimum set of coins that make a given value

math

dynamic-programming

greedy