相关疑难解决方法(0)

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

“给定值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代表每种硬币面额。

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

问题链接：

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

提前致谢。我访问的每个网站仅说明了该解决方案的工作原理，而不说明其他解决方案为何不起作用。

我编写了一个用于生成子集和的程序,该程序可能会在此问题中使用,该程序指出:

假设你有3个1美元硬币,2个2美元硬币,3个5美元硬币,1个10美元硬币,有4种方法从这些硬币中获得10美元.如果有n1 $ X1币,n2 $ X2币...... nm $ Xm币,我们有多少种方法可以从这些有限数量的硬币中获得$ X？

如果我们创建一组{X1,X1 ..... X1,X2,X2 .......... X2,...,...,.......... ..,Xm,Xm ... Xm},然后对它运行Subset求和,当然我们可以得到$ X的结果.但是我找不到使用集合{n1,n2,n3 ...... nm},{X1,X2,X3 ...... Xm}的方法.一位朋友告诉我,这是背包问题的变种,但我不确定,怎么样.

这是我写的部分代码:

ways[0]=1, mylim=0;
for(i=0;i<count;i++){
    if(mylim+coins[i]<=LIMIT) mylim+=coins[i];
    else mylim=LIMIT;

    for(j=mylim; j>=coins[i];j--){
        ways[j]=(ways[j]+ways[j-coins[i]])%MOD;
    }
}

如果你能够精心解释一下,那对我来说会很棒.

编辑:这个问题更适合计算机科学的堆栈交换,但由于这是我的一个老问题,我宁愿在这里编辑它.

这个问题可以通过包含排除原则来解决,当我们固定硬币值但每个硬币的数量随每个查询而变化时,它会派上用场.

假设,方法[v]是使用$ x1,$ x2,.. $ xm制作$ v的方法,每种方法根据需要多次使用.现在,如果我们只使用N1的数字$ X1,我们必须减去至少使用(配置N1 + 1)号的$ X1(这实际上是方法 [ N - (N1 + 1)×1 ]).此外,如果我们只使用N2的数字 …