动态规划和0/1背包问题

Question

我阅读了很多资源，但仍然有些难以理解动态规划。

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

以下是相关幻灯片：

我基本上能理解发生了什么，直到最后一张幻灯片，其中写着 f(i,y) = max{....}

我到底在找什么的最大值？为什么要找任何东西的最大值？最重要的是，这与动态规划有什么关系？我不理解它们之间的关系，就像我理解斐波那契示例时那样。老实说，我真的不知道这个背包问题与动态规划有任何关系，因为它似乎根本无法与使用斐波那契示例说明动态规划相比较。我看不到任何相似之处或者其他任何东西，它对我来说真的没有多少意义。

- FrostyStraw

---

最大值说：选或不选，选最好的。 - keyser

这些链接可能会有所帮助： http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-15-dynamic-programming-longest-common-subsequence/ 和 http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/video-lectures/ - arunmoezhi

你应该试试这个：http://people.cs.clemson.edu/~bcdean/dp_practice/dp_0.swf 和 http://people.cs.clemson.edu/~bcdean/dp_practice/ - grdvnl

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)最多包含一个项目，而不是按递减的i并在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}

如果您仍然难以理解，我建议您自己构建一个示例来进行实际操作 - 无论多少解释都不如看到它真正工作并使用它来获得一些关于为什么我们这样做的直觉。

- Bernhard Barker

---

所以当你说我们是根据包含更少物品和可能更小的容量的问题来定义它时，在这个特定的例子中，它是从最后一个项目向后工作，确定n-1号项目是否进入背包，基于我们为n决定的内容，并且我们基于n-1和n是否进入来确定n-2是否进入等等？ 例如，如果有3个项目，我们首先会做f(1,y) = max(f(2,y), f(2,y-w_1)+p_1}，但直到我们到达第n个项目，我们才能得到利润，然后它就会在那之后倒退？@Dukeling - FrostyStraw

这是否类似于递归，其中基本情况是第n项，并返回值（或决策），直到返回到第1项？ - FrostyStraw

如果我刚才描述的是正确的，那么这是否是使用记忆化或“自顶向下”的动态规划方法的示例？ - FrostyStraw

这太令人困惑了。我构建了以下示例：w = [3, 2, 10] 和 p = [9, 5, 1]，总容量为11，n=3个物品。所以我们从f(n,y)开始，即f(3,11)...因为w_3 < y，那么f(n,y) = p_n = 1。那是什么意思？把它放进背包的利润是1，但我们还没有决定放吗？然后我猜我们从那里到f(2,y) = max {f(3,y), f(3, y-w_2) + p_2 }。所以这意味着放置2的利润是放置或不放置3的利润的最大值？当我们到达f(2,y)时，y是将3添加到背包后的价值吗？ - FrostyStraw

@codemania23，我在答案中添加了更多细节。 - Bernhard Barker

Answer 2

我到底要找什么的最大值？

f是你放入背包中的所有物品带来的利润总和。在第i阶段，有两种可能性：

• 你将物品i放入背包中，并解决剩余物品的问题，从最大重量中减去物品i的重量。
• 你不将物品i放入背包中，并解决剩余物品的问题。这是一个子问题，因为你正在向后工作，所以与动态规划的联系应该在那里变得明显。

解决方案是带来最高利润的选项，因此是最大值。

- Zoyd

---

你是如何逆推的？如果你从第i项开始，然后到达i+1项，那似乎不是在逆推 @Zoyd - FrostyStraw

提议的解决方案从 i = n 到 i = 1 工作。这就是我所说的“向后”工作，与递归算法相反，其中基本情况是 i = 1。我想我本可以让它更清晰明了。@FrostyStraw - Zoyd

@Zoyd，请解释一下重叠子问题在哪里？我已经把它写在纸上了，但似乎找不到任何重叠的问题。 - codemania23