转硬币

Question

我正试图解决一个经典的动态规划硬币兑换问题。这是一个家庭作业问题，我不是在寻找完整的解决方案，只是想找几个指针看看我做错了什么。

输入：

• 金额x我们想用硬币支付一些价值
• 集合d表示面值（1c、5c、10c、25c、100c、200c）的可用硬币数量

输出：

• 需要换手支付的最低硬币数。

假设：

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

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

我试图建立一个数组C，使得每个元素C[i]，是 /minimum/数量的硬币，交换手的数量i。

C[0]=0

对于C[i]，我计算它的方法是，对于所有可用面额的硬币，取所有C[i-di]加1的最小值。然后，我从可用硬币中取出硬币。

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

99 99 0 0 0 1 0

我的方法失败了，因为用1美元兑换2枚硬币比用99美分（99枚硬币兑换）更“便宜”。

任何指点都将不胜感激。

Answer 1

要点：你可以对硬币进行重复。

解决方案：构建一个数组，其中ARR[i]=生成值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

Answer 2

问题似乎是，当你找到你想要的价值时，你就会停下来。如果您继续，计算出使值大于x的最小硬币数，然后将最小硬币数添加到该值上，以便注册操作员进行适当更改，并从这个较大的列表中获取最小硬币数，您应该能够回答这个问题。

编辑：如果使用两个数组，一个用于可以生成的值，另一个用于寄存器可以生成的值，则可以稍微简化此操作。然后你可以通过某种方式比较它们来得到你的答案。