7

我正在尝试解决一个经典的动态编程硬币找零问题。这是一个家庭作业问题，我不是在寻找完整的解决方案，只是为了看看我做错了什么。

输入：

  • 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 个硬币）更“便宜”。

任何指针将不胜感激。

4

2 回答 2

1

问题似乎是当你达到你正在寻找的价值时你会停下来。如果您继续前进，找出使值大于 x 的最小硬币数量，然后将最小硬币数量添加到寄存器操作员以进行适当更改，并从这个较大的列表中取最小值，您应该能够回答这个问题。

编辑：如果您使用两个数组，您可以稍微简化这一点，一个用于您可以制作的值，一个用于寄存器可以制作的值。然后你可以以某种方式比较它们以获得你的答案。

于 2012-07-03T23:02:16.903 回答
0

要点：硬币可以重复。

解决方案：构建一个数组，其中 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
于 2015-02-01T01:54:16.660 回答