algorithm - 动态规划和 0/1 背包

Question

我在理解动态规划时遇到了一些困难，尽管我已经通读了很多资源试图理解。

我理解使用斐波那契算法给出的动态规划示例。我明白如果你使用分而治之的方法，你最终会多次解决一些子问题，而动态编程通过解决这些重叠的子问题来解决这个问题，但只解决一次(并将它们存储起来以备将来引用) .但是，我在类里面以 0/1 背包问题为例向我介绍了动态编程，但我并不真正理解这个例子，或者它如何说明动态编程，或者它与斐波那契示例的相似之处.

这是相关的幻灯片:

我主要了解发生了什么，直到最后一张幻灯片，上面写着 f(i,y) = max{....}

我到底找到了什么？为什么我会找到任何东西的最大值？最重要的是，这与动态规划有什么关系？我不明白这种关系，就像我在谈到斐波那契例子时所做的那样。老实说，我不知道这个背包问题与动态规划有什么关系，因为它看起来甚至无法与使用斐波那契示例来说明动态规划相提并论。就像我看不到任何相似之处或任何东西一样，这对我来说真的没有多大意义

Answer 1

动态规划只是根据更简单的子问题来定义问题。

对于斐波那契数列，我们根据两个较小的项来定义问题。

在这种情况下，我们根据包含较少项目和可能较小容量的子问题来定义具有一定数量项目和一定容量的问题。

我们开始计算最多 1 个项目和每个容量的利润。然后我们计算最多 2 个项目和每个容量的利润。然后我们对最多 3 个项目执行此操作，然后是 4 个，依此类推。由于我们根据具有较少项目的子问题定义了一个问题，因此我们可以简单地查找我们已经计算的内容以确定具有 2、3、4 等项目的任何值。

将此视为物理二维网格可能会有所帮助，您可以在其中从一个方向向另一个方向填充值，并且每次您只查看所有值已填充的方向。

存在重叠的子问题，因为在一种情况下我们使用相同的容量，而在另一种情况下我们使用较小的容量。较小的容量有时会匹配检查相同容量的不同子问题。也就是说，一个问题的 f(i+1, j) 将等于另一个问题的 f(i+1, y - w_i)。例如，您可以看到 f(11, 5) 出现在两个地方:

f(10, 8) = max(f(11, 8), f(11, 5) + 77)   // w_i = 3
f(10, 5) = max(f(11, 5), f(11, 2) + 77)

在这种情况下，我们已经为每个 X 计算了 f(11, X)，因此我们可以只查找这些值。

我确实发现我们根据增加 i 来定义问题有点令人困惑，如 f(i, j) = ...f(i+1, X)... 并且 f(n, X) 因此最多包含 1 个项目，而不是使用递减的 i 并且最多包含 1 个项目f(1, X)。但这只是语义，不会以任何方式改变问题。

技术细节解释

f(i,y) 是包含项目 i 到 n 的子集的最大利润，容量为 y 。

现在我们可以将其定义为包括或排除项目 i，然后获得项目 i+1 到 n 的最大利润.

当我们排除项目 i 时，这不会改变权重，所以我们可以只看相同容量的最大利润，即 f(i+1, y) ，利润也没有变化。

当我们包含项目 i 时，这会改变权重，特别是项目 i 的权重，即 w_i，所以我们有查找 f(i+1, y - w_i)。但随后我们也获得了商品i的利润，所以我们需要加上它的利润，即p_i。

现在，因为我们想要最大的利润，我们必须找到这两个值中的最大值，给我们:

f(i, y) = max{f(i+1, j), f(i+1, y - w_i) + p_i}

---

如果您仍然无法理解它，我建议您自己构建一个示例来完成 - 没有多少解释完全可以看到它实际工作，并使用它来获得一些关于我们为什么做事的直觉我们的方式。