变革：动态规划

Question

在之前的一次讲座中，我们被告知使用贪婪方法来解决变革问题并不总是有效。

举个例子如下：

我们想要达到

n = 14

，我们有三种不同价值的硬币：

d1 = 1

，

d2 = 7

，

d3 = 10

。

使用贪婪方法，这将导致我们做

10 + 1 + 1 + 1 + 1

（5个硬币）。

据说动态问题方法可以准确地解决这个问题。我试着算了一下，但结果又回到了 5。

假设F持有金额所需的硬币数量

F[14] = min {F[14 – 1] , F[14 – 7],  F[14 – 10]} + 1

      = F[14 – 10] + 1 = 4 + 1 = 5

这再次表明我们需要 5 个硬币，而这显然可以通过使用 2 个硬币（7 + 7）来完成。

什么给予？谢谢。

Answer 1

您假设了

min {F[14 – 1] , F[14 – 7],  F[14 – 10]}=F[14-10]

，但事实并非如此。最小值实际上是

F[14-7]=1

，因此最优值是

2