9

我在理解各种问题的动态编程解决方案方面遇到问题，特别是硬币找零问题：

“给定一个值 N，如果我们想找 N 美分，并且我们有无限供应 S = { S1, S2, .. , Sm} 价值的硬币，我们有多少种方法可以找零？顺序硬币没关系。

例如，对于 N = 4 和 S = {1,2,3}，有四种解：{1,1,1,1},{1,1,2},{2,2},{1, 3}。所以输出应该是 4。对于 N = 10 和 S = {2, 5, 3, 6}，有五种解决方案：{2,2,2,2,2}，{2,2,3,3}， {2,2,6}、{2,3,5} 和 {5,5}。所以输出应该是 5。”

这个问题还有另一种变体，其中解决方案是满足数量的最小硬币数量。

这些问题看起来非常相似，但解决方案却大不相同。

进行更改的可能方法的数量：对此的最佳子结构是DP(m,n) = DP(m-1, n) + DP(m, n-Sm)其中 DP 是所有硬币的解决方案数第 m 个硬币和金额 = n。

最小硬币数量：最佳子结构是 DP[i] = Min{ DP[i-d1], DP[i-d2],...DP[i-dn] } + 1其中 i 是总金额d1..dn 代表每个硬币面额。

为什么第一个需要二维数组而第二个需要一维数组？为什么改变方法数量的最佳子结构不是“ DP[i] = DP[i-d1]+DP[i-d2]+...DP[i-dn] ”，其中 DP[i] 是i 数量可以通过硬币获得的方式数量。这对我来说听起来合乎逻辑，但它会产生一个不正确的答案。为什么在这个问题中需要硬币的第二维，但在最小数量问题中不需要？

问题链接：

http://comproguide.blogspot.com/2013/12/minimum-coin-change-problem.html http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

提前致谢。我访问的每个网站都只解释解决方案的工作原理，而不是为什么其他解决方案不起作用。

4

2 回答 2

6
  1. 让我们先谈谈方式的数量，DP(m,n) = DP(m-1, n) + DP(m, n-Sm)。这确实是正确的，因为您可以使用第 m 个面额，也可以避免使用它。现在你说我们为什么不把它写成DP[i] = DP[i-d1]+DP[i-d2]+...DP[i-dn]。那么这会导致过度计数，让我们举个例子，其中 n=4 m=2 和 S={1,3}。现在根据您的解决方案 dp[4]=dp[1]+dp[3]。（假设 1 是基本情况 dp[1]=1）。现在 dp[3]=dp[2]+dp[0]。（在基本情况下再次 dp[0]=1 ）。再次应用相同的 dp[2]=dp[1]=1。因此，当它应该只是 2 （ (1,3) 和 (1,1,1,1) ）时，您总共会得到 3 的答案。之所以如此，是因为您的第二种方法将（1,3）和（3,1）视为两个不同的解决方案。您的第二种方法可以应用于顺序很重要的情况，这也是一个标准问题。

  2. 现在对于你的第二个问题，你说最小面额数可以通过DP[i] = Min{ DP[i-d1], DP[i-d2],...DP[i-dn] } + 1 . 好吧，这是正确的，因为在找到最小面额时，订单或无订单都无关紧要。为什么这是线性/一维 DP ，尽管 DP 数组是一维的，但每个状态最多取决于 m 个状态，这与您的第一个解决方案不同，其中数组是二维的，但每个状态最多取决于 2 个状态。因此，在这两种情况下，运行时间（状态数 * 每个状态所依赖的状态数）都是相同的，即O(nm)。所以两者都是正确的，只是你的第二个解决方案可以节省内存。因此，您可以通过一维数组方法找到它，也可以通过使用递归 dp(n,m)=min(dp(m-1,n),1+dp(m,n-Sm))找到它. （只需在您的第一次重复中使用 min ）


    希望我消除了疑虑，如果仍有不清楚的地方，请发布。

于 2015-03-07T03:35:09.040 回答
0

这是使用动态编程对硬币找零问题的一个很好的解释。

代码如下：

public static int change(int amount, int[] coins){
    int[] combinations = new int[amount + 1];

    combinations[0] = 1;

    for(int coin : coins){
        for(int i = 1; i < combinations.length; i++){
            if(i >= coin){
                combinations[i] += combinations[i - coin];
                //printAmount(combinations);
            }
        }
        //System.out.println();
    }

    return combinations[amount];
}
于 2017-10-28T23:02:55.123 回答