动态规划和 0/1 背包

尽管我已经阅读了很多资源试图理解动态编程，但我在理解动态编程方面遇到了一些困难。

我理解使用斐波那契算法给出的动态规划的示例。我明白如果你使用分而治之的方法，你最终会多次解决一些子问题，而动态编程通过解决这些重叠的子问题但只解决一次（并存储它们以供将来参考）来解决这个问题。然而，我在课堂上以 0/1 背包问题为例介绍了动态规划，但我并不真正理解这个示例，或者它如何说明动态规划，或者它与斐波那契示例有何相似之处。

以下是与之相关的幻灯片：

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

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

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

就斐波那契数列而言，我们用两个较小的项来定义问题。

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

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

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

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

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)

在这种情况下我们已经计算过f(11, X)对于每一个X，所以我们可以查找这些值。

我确实觉得我们用增加来定义问题有点令人困惑i, as in 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)。但我们也从 item 中获得利润i，所以我们需要加上它的利润，即p_i.

现在，由于我们想要最大利润，我们必须找到这两个值的最大值，给出：

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

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