硬币-有变化的变化

Question

我试图解决一个经典的动态规划硬币变化问题。这是一个家庭作业问题，我并不是在寻找完整的解决方案，只是为了看看我做错了什么。

输入：

• 我们想用硬币支付一定价值的x金额。
• 集合d表示可用的面额硬币数(1c，5c，10c，25c，100c，200c)

输出：

• 最低数量的硬币，需要交换的手付款。

假设：

• 收银机操作员有无限的硬币供应，并知道如何给出最佳的变化。

到目前为止，我试图做的是：

我正在尝试构建一个数组C，这样每个元素Ci都是用来交换数量i的/最小/数量的硬币。

C=0

对于Ci，我通过取所有Ci-di加1的最小值来计算，对于所有可用的硬币面额。然后我从可用的硬币中取出我挑选的硬币。

这种方法似乎适用于简单的情况，但当我这样做时，例如：

99 99 0 0 0 1

我的方法失败了，因为用1美元兑换两枚硬币要比付99美分(兑换99枚硬币)更“便宜”。

任何指示都将不胜感激。

Answer 1

问题似乎是，当你到达你想要的价值时，你就停止了。如果你继续，计算出硬币的最小数量，使数值大于x，然后再加上寄存器操作符的最小硬币数来进行适当的更改，并从这个较大的列表中取最小值，你应该能够回答这个问题。

编辑:如果使用两个数组，一个用于可以生成的值，另一个用于寄存器可以生成的值，则可以稍微简化这一点。然后你可以用某种方式来比较这些来得到你的答案。

Answer 2

关键点:你可以有重复的硬币。

解决方案:构建一个数组，其中ARRi =最小数量的硬币使值i。

一些伪码：

ARR[MAX] = {MAXIMUM VALUE} // set all elements in the array to have some big value
ARR[0] = 0

for C in coins
 for i = 0; i <= needed_value; ++i
   if i+C <= needed_value && ARR[i+C] > ARR[i]+1
     ARR[i+C] = ARR[i]+1

Example:
coins = {1, 3}
needed_value = 8
ARR[] = 0 INF INF INF INF INF INF INF INF
after using the coin with value 3, we will have
ARR[] = 0 INF INF 1 INF INF 2 INF INF
after using the coin with value 1, we will have
ARR[] = 0 1 2 1 2 3 2 3 4
=> we need 4 coins to make the sum