变革:动态规划

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