use*_*043 7 algorithm dynamic-programming
我试图通过扭曲来解决经典的动态编程硬币变化问题.这是一个家庭作业的问题,我不是在寻找完整的解决方案,只是为了指出我做错了什么.
输入:
x,我们想在硬币支付一定的价值.d面额的硬币可用(1C,5C,10C,25C,100C,200C)的代表数输出:
假设:
到目前为止我试图做的事情:
我正在尝试构建一个数组C,这样每个元素C [i],是最小/用于交换金额i的硬币数量.
C [0] = 0
对于C [i],我通过对所有可用的硬币面额采取最小的所有C [i-di]加1来计算它.然后我从可用的硬币中取出我挑选的硬币.
这种方法似乎在简单的情况下工作,但是当我有,例如:
99 99 0 0 0 1 0
我的方法失败了,因为它"便宜"到1美元,它将产生2个硬币的交换,而不是支付精确的99美分(交换99个硬币).
任何指针将不胜感激.
问题似乎在于，当您达到所需的值时，您就会停下来。如果你继续下去，计算出使值大于 x 的最小硬币数量，然后添加寄存器操作员进行适当更改的最小硬币数量，并从这个较大的列表中取出最小值，你应该能够来回答这个问题。
编辑：如果您使用两个数组，一个用于您可以创建的值，另一个用于寄存器可以创建的值，您可以稍微简化这一点。然后你可以通过某种方式比较它们来得到你的答案。