当每种硬币只有一种可用时，修改了硬币交换问题

Question

给定一组面值和总数，我们必须找到使总数精确所需的最低硬币数量。

约束：每个面额的硬币只有一枚。

你如何比较贪婪方法和动态规划方法？

编辑：例如：我有面额为1、2、3、5的现金。我每种面额只有一枚硬币。我想用最少数量的硬币换11英镑的零钱。答案是4（1235）。如果我有无限量的每种面额，答案是3（551或533）。

Answer 1

找到任何解，更不用说最大解，都被称为子集和问题。它是NP完全的，并且最有效的已知算法具有指数运行时间。

因此，贪婪算法不适用于此问题。您不会比某种回溯搜索做得更好。使用动态规划的解决方案实际上相当于回溯搜索，只是实现方式不同而已。因此，比较非常简短：贪婪不起作用，但动态规划可以。

Answer 2

你如何比较贪婪方法和动态规划方法？

贪婪的方法在你的情况下会失败，因为你永远不知道什么时候该跳过或拿硬币来得到最好的答案。你必须尝试所有可能的解决方案，包括/排除每一枚硬币。

例如，您可以使用使用相同硬币变化算法的动态编程来实现这一点，但避免多次使用相同的硬币

递归自上而下方法：

int n = 4, k = 11;
int dp[4][12], coins[] = {1, 2, 3, 5};

int solve(int i = 0, int sm = k) {
    // base case for when the sum is reached
    if (sm == 0) {
        return 0;
    }
    // took more than needed coins or reached the end without reaching sum
    if (sm < 0 || i == n) {
        return 1000000000;
    }
    // check if dp value already calculated
    int& ret = dp[i][sm];
    if (~ret) {
        return ret;
    }
    // otherwise, try taking the coin or skipping it
    return ret = min(solve(i+1, sm), 1 + solve(i+1, sm-coins[i]));
}
int main() {
    memset(dp, -1, sizeof dp);
    cout << solve() << endl;
 return 0;
}
// output: 4