首页 文章

动态编程 - 硬币

提问于
浏览 次
3

考虑下面的一段伪代码，其中 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]] - >我真的没有得到这个部分，你为什么要用它，有人可以向我解释一下！

algorithm dynamic-programming

1 回答

  • 4

    为了回答您的问题，您需要了解每个变量代表什么，以及算法的高级别 .

    算法到达解决方案的过程会尝试计算从 1 到 n （包括）的所有金额进行更改所需的硬币数 . 这就是外循环的目的：它从 1 到 n 迭代当前的"goal"，让循环体提出该目标的答案 .

    从本质上讲，算法是这样的：

    • 我知道如果金额为零，我需要零硬币才能做出改变

    • 看看我需要换多少枚硬币 1

    • 知道我需要改变多少硬币 1 ，看看我需要换多少硬币 2

    • 知道我需要通过 2 进行多少硬币更改 1 ，查看我需要更换多少硬币 3

    • 知道需要多少钱才能通过 1 进行更改 1 ，查看我需要更换多少钱币 4

    • ......

    • 知道我需要改变多少硬币 1 到 n-1 ，看看我需要换多少硬币 n

    p 的值代表当前目标 - 即我们尝试进行更改的金额 . 数组 C 表示我们迄今为止从 1 到 p-1 （包括）的所有金额找到的解决方案 .

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

    现在您已经准备好了解 1 + C[p-d[i]] 的含义：我们正在尝试为 p 进行更改，因此 C[p-d[i]] 是为 p-d[i] 提出更改所需的最小硬币数量 . 因此，公式说“如果我知道需要 x 硬币才能对 p-d[i] 进行更改，并且我有一个面值为 d[i] 的硬币，那么我可以通过添加一个 d[i] 硬币来达到 p （因此，表达式的 1 + ... 部分） ） .

    回复于

相关问题