动态规划 - 零钱问题

Question

考虑以下伪代码片段，其中d是面额值数组，k是面额数量，n是需要找零的金额。

Change(d; k; n)
1 C[0]  <- 0
2 for p <-  1 to n
3     min  <- INFINITE
4     for i  <- 1 to k
5         if d[i] <= p then
6           if 1 + C[p - d[i]] < min then
7               min  <- 1 + C[p - d[i]]
8               coin  <- i
9     C[p] <-  min
10    S[p] <-  coin
11 return C and S

我已经阅读了很多关于这个特定问题的信息，但我仍然不明白为什么： 1 + C[p-d[i]] --> 我真的不明白这一部分，你为什么要使用它？能否有人给我解释一下！

- FraK

Answer 1

为了回答你的问题，你需要理解每个变量代表什么，以及算法在高层次上正在做什么。

该算法到达解决方案的过程尝试计算从1到n（包括1和n）的所有金额所需的硬币数量。这就是外部循环的目的：它迭代当前“目标”从1到n，使循环体为该目标提供答案。

本质上，算法如下：

我知道如果金额为零，我需要零个硬币来找零

看看我需要多少枚硬币才能找零 1

知道我需要多少枚硬币才能找零 1，看看我需要多少枚硬币才能找零 2

知道我需要多少枚硬币才能找零 1 到 2，看看我需要多少枚硬币才能找零 3

知道我需要多少枚硬币才能找零 1 到 4，看看我需要多少枚硬币才能找零 4

...

知道我需要多少枚硬币才能找零 1 到 n-1，看看我需要多少枚硬币才能找零 n

变量p的值表示当前目标即为我们试图找零的金额。数组C表示到目前为止我们已经找到的解决方案，包括从1到p-1的所有金额。

对于每个金额，算法尝试使用每种面额d[i]的硬币来找到一个解决方案。

现在你可以理解1 + C[p-d[i]]的含义了：我们正在尝试找零

的钱，因此C[p-d[i]]是找零

-d[i]

所需的最小硬币数。因此，该公式表明：“如果我知道需要x枚硬币才能找零

-d[i]

，并且我有一枚面额为d[i]的硬币，则我可以通过添加一枚d[i]硬币（因此是1 + ...部分的表达式）来达到

。”

- Sergey Kalinichenko

---

@FraK 当你到达p=4时，你的C []会像这样：{0: 0、1:1、2:1、3:2}。这意味着单个硬币可以制作出1和2，而需要2个硬币才能制作出3。因此，现在内部循环将尝试将C [4]设置为某个值。它将尝试使用d [0]，检查C [4-d [0]]（即C [3]，其等于2），并表示需要一个额外的面值为1的硬币才能从3制作出4。它将设置C [4] = 3，然后继续下一个硬币。下一个硬币是2，所以算法将看到1+C [4-2]小于C [4]，并将C [4]设置为2。 - Sergey Kalinichenko

感谢您的全面解释，我已经理解了除了最后一部分。假设我们有d = {1,2,5}，并且我的p = 4，在内部循环中：(d [0] = 1) <= 4，然后如果(1 + c [4-1]) <= INFINITE，这将产生：1 + 2 <= INFINITE，最终min = 3，我真的不明白这里的逻辑，请向我解释一下，我的意思是我知道它可以工作，但我不知道为什么？更具体地说，为什么要减去d [i]的位置！！！ - FraK

没事，我已经想通了！你说的完全正确，尽管我可能从另一个角度看待它，用其他的术语来表述： - FraK

如果我选择d[i]（面值）作为解决方案的一部分，那意味着我将使用一个面值为d[i]的硬币，它可以是{1, 2, 5}之一。但我仍然需要计算出达到我的目标p所需的硬币数量总和，直到现在，我只选择了一个面值为d[i]的硬币，现在我需要添加我需要完成目标p的硬币数量，这将是p-d[i]，即我的目标减去我选择使用的硬币d[i]的数量。就是这么简单，我的困惑在于硬币数量和d[i]中实际价值。非常感谢您的帮助！希望这可以帮助其他人。 - FraK