0/1 背包问题

背包在这里就像一个容器或袋子。假设我们给出了一些物品，它们有重量或利润。我们必须以一种方式将一些物品放入背包，以使总价值产生最大利润。

例如，容器的重量是 20 公斤。我们必须选择物品，使物品的总重量小于或等于容器的重量，并且利润最大化。

背包问题有两种类型：

• 0/1 背包问题
• 分数背包问题

我们将逐一讨论这两种问题。首先，我们将学习 0/1 背包问题。

什么是 0/1 背包问题？

0/1 背包问题意味着物品要么完全装入背包，要么完全不装入背包。例如，我们有两个物品，重量分别为 2 公斤和 3 公斤。如果我们选择 2 公斤的物品，那么我们不能从 2 公斤的物品中选择 1 公斤的物品（物品不可分割）；我们必须完整地选择 2 公斤的物品。这是一个 0/1 背包问题，在这种问题中，我们要么完全选择该物品，要么根本不选择该物品。0/1 背包问题可以通过动态规划来解决。

什么是分数背包问题？

分数背包问题意味着我们可以分割物品。例如，我们有一个 3 公斤的物品，那么我们可以选择 2 公斤的物品，而放弃 1 公斤的物品。分数背包问题可以通过贪心算法来解决。

0/1 背包问题示例。

考虑以下重量和利润问题：

重量：{3, 4, 6, 5}

利润：{2, 3, 1, 4}

背包的重量是 8 公斤

物品数量是 4

上述问题可以使用以下方法解决：

x_i = {1, 0, 0, 1}

= {0, 0, 0, 1}

= {0, 1, 0, 1}

以上是可能的组合。1 表示完全选择了该物品，0 表示未选择任何物品。由于有 4 个物品，因此可能的组合将是

2⁴ = 16；所以。通过使用上述问题可以进行 16 种可能的组合。一旦所有组合都完成，我们就必须选择能够产生最大利润的组合。

解决该问题的另一种方法是动态规划方法。在动态规划方法中，复杂问题被分解为子问题，然后我们找到子问题的解，子问题的解将用于找到复杂问题的解。

如何通过动态规划方法解决此问题？

首先，

我们创建一个如下所示的矩阵

在上表中，列代表重量，即 8。行代表物品的利润和重量。这里我们没有直接取重量 8，问题被分解为子问题，即 0、1、2、3、4、5、6、7、8。子问题的解将存储在单元格中，问题的答案将存储在最终单元格中。首先，我们将重量按升序排列，利润根据其重量排列，如下所示：

w_i = {3, 4, 5, 6}

p_i = {2, 3, 4, 1}

第一行和第一列将为 0，因为 w=0 时没有物品

当 i=1，W=1 时

w₁ = 3；由于集合中只有一个重量为 3 的物品，但背包的容量是 1。我们无法将 3 公斤的物品放入容量为 1 公斤的背包中，因此在 M[1][1] 中添加 0，如下所示：

当 i = 1，W = 2 时

w₁ = 3；由于集合中只有一个重量为 3 的物品，但背包的容量是 2。我们无法将 3 公斤的物品放入容量为 2 公斤的背包中，因此在 M[1][2] 中添加 0，如下所示：

当 i=1，W=3 时

w₁ = 3；由于集合中只有一个重量等于 3 的物品，而背包的重量也等于 3；因此，我们可以用重量等于 3 的物品装满背包。我们将与重量 3 对应的利润，即 2，放在 M[1][3] 中，如下所示：

当 i=1，W = 4 时

_W1 = 3；由于集合中只有一个重量等于 3 的物品，而背包的重量是 4；因此，我们可以用重量等于 3 的物品装满背包。我们将与重量 3 对应的利润，即 2，放在 M[1][4] 中，如下所示：

当 i=1，W = 5 时

_W1 = 3；由于集合中只有一个重量等于 3 的物品，而背包的重量是 5；因此，我们可以用重量等于 3 的物品装满背包。我们将与重量 3 对应的利润，即 2，放在 M[1][5] 中，如下所示：

当 i =1，W=6 时

_W1 = 3；由于集合中只有一个重量等于 3 的物品，而背包的重量是 6；因此，我们可以用重量等于 3 的物品装满背包。我们将与重量 3 对应的利润，即 2，放在 M[1][6] 中，如下所示：

当 i=1，W = 7 时

_W1 = 3；由于集合中只有一个重量等于 3 的物品，而背包的重量是 7；因此，我们可以用重量等于 3 的物品装满背包。我们将与重量 3 对应的利润，即 2，放在 M[1][7] 中，如下所示：

当 i =1，W =8 时

_W1 = 3；由于集合中只有一个重量等于 3 的物品，而背包的重量是 8；因此，我们可以用重量等于 3 的物品装满背包。我们将与重量 3 对应的利润，即 2，放在 M[1][8] 中，如下所示：

现在 'i' 的值递增，变成 2。

当 i =2，W = 1 时

值 2 对应的重量是 4，即 w₂ = 4。由于集合中只有一个重量等于 4 的物品，而背包的重量是 1。我们无法将重量为 4 的物品放入背包中，因此在 M[2][1] 中添加 0，如下所示：

当 i =2，W = 2 时

值 2 对应的重量是 4，即 w₂ = 4。由于集合中只有一个重量等于 4 的物品，而背包的重量是 2。我们无法将重量为 4 的物品放入背包中，因此在 M[2][2] 中添加 0，如下所示：

当 i =2，W = 3 时

值 2 对应的重量是 4，即 w₂ = 4。由于集合中有重量为 3 和 4 的两个物品，而背包的重量是 3。我们可以将重量为 3 的物品放入背包中，因此在 M[2][3] 中添加 2，如下所示：

当 i =2，W = 4 时

值 2 对应的重量是 4，即 w₂ = 4。由于集合中有重量为 3 和 4 的两个物品，而背包的重量是 4。我们可以选择重量为 4 的物品放入背包，因为重量为 4 的物品的利润高于重量为 3 的物品，因此在 M[2][4] 中添加 3，如下所示：

当 i = 2，W = 5 时

值 2 对应的重量是 4，即 w₂ = 4。由于集合中有重量为 3 和 4 的两个物品，而背包的重量是 5。我们可以选择重量为 4 的物品放入背包，其对应的利润为 3，因此在 M[2][5] 中添加 3，如下所示：

当 i = 2，W = 6 时

值 2 对应的重量是 4，即 w₂ = 4。由于集合中有重量为 3 和 4 的两个物品，而背包的重量是 6。我们可以选择重量为 4 的物品放入背包，其对应的利润为 3，因此在 M[2][6] 中添加 3，如下所示：

当 i = 2，W = 7 时

值 2 对应的重量是 4，即 w₂ = 4。由于集合中有重量为 3 和 4 的两个物品，而背包的重量是 7。我们可以选择重量为 4 和 3 的物品放入背包，它们的总利润为 (2 + 3) = 5，因此在 M[2][7] 中添加 5，如下所示：

当 i = 2，W = 8 时

值 2 对应的重量是 4，即 w₂ = 4。由于集合中有重量为 3 和 4 的两个物品，而背包的重量是 7。我们可以选择重量为 4 和 3 的物品放入背包，它们的总利润为 (2 + 3) = 5，因此在 M[2][7] 中添加 5，如下所示：

现在 'i' 的值递增，变成 3。

当 i = 3，W = 1 时

值 3 对应的重量是 5，即 w₃ = 5。由于集合中有重量为 3、4 和 5 的三个物品，而背包的重量是 1。我们无法将任何物品放入背包中；因此，在 M[3][1] 中添加 0，如下所示：

当 i = 3，W = 2 时

值 3 对应的重量是 5，即 w₃ = 5。由于集合中有重量为 3、4 和 5 的三个物品，而背包的重量是 1。我们无法将任何物品放入背包中；因此，在 M[3][2] 中添加 0，如下所示：

当 i = 3，W = 3 时

值 3 对应的重量是 5，即 w₃ = 5。由于集合中有重量分别为 3、4 和 5 的三个物品，而背包的重量是 3。可以将重量为 3 的物品放入背包，其对应的利润为 2，因此在 M[3][3] 中添加 2，如下所示：

当 i = 3，W = 4 时

值 3 对应的重量是 5，即 w₃ = 5。由于集合中有重量分别为 3、4 和 5 的三个物品，而背包的重量是 4。我们可以选择重量为 3 或 4 的物品；重量为 4 的物品的利润 (3) 比重量为 3 的物品的利润更高，因此在 M[3][4] 中添加 3，如下所示：

当 i = 3，W = 5 时

值 3 对应的重量是 5，即 w₃ = 5。由于集合中有重量分别为 3、4 和 5 的三个物品，而背包的重量是 5。我们可以选择重量为 3、4 或 5 的物品；重量为 4 的物品的利润 (3) 比重量为 3 和 5 的物品的利润更高，因此在 M[3][5] 中添加 3，如下所示：

当 i =3，W = 6 时

值 3 对应的重量是 5，即 w₃ = 5。由于集合中有重量分别为 3、4 和 5 的三个物品，而背包的重量是 6。我们可以选择重量为 3、4 或 5 的物品；重量为 4 的物品的利润 (3) 比重量为 3 和 5 的物品的利润更高，因此在 M[3][6] 中添加 3，如下所示：

当 i =3，W = 7 时

值 3 对应的重量是 5，即 w₃ = 5。由于集合中有重量分别为 3、4 和 5 的三个物品，而背包的重量是 7。在这种情况下，我们可以同时选择重量为 3 和 4 的物品，总利润为 (2 + 3) = 5，因此在 M[3][7] 中添加 5，如下所示：

当 i = 3，W = 8 时

值 3 对应的重量是 5，即 w₃ = 5。由于集合中有重量分别为 3、4 和 5 的三个物品，而背包的重量是 8。在这种情况下，我们可以同时选择重量为 3 和 4 的物品，总利润为 (2 + 3) = 5，因此在 M[3][8] 中添加 5，如下所示：

现在 'i' 的值递增并变为 4。

当 i = 4，W = 1 时

值 4 对应的重量是 6，即 w₄ = 6。由于集合中有重量分别为 3、4、5 和 6 的四个物品，而背包的重量是 1。所有物品的重量都大于背包的重量，因此我们无法将任何物品添加到背包中；因此，在 M[4][1] 中添加 0，如下所示：

当 i = 4，W = 2 时

值 4 对应的重量是 6，即 w₄ = 6。由于集合中有重量分别为 3、4、5 和 6 的四个物品，而背包的重量是 2。所有物品的重量都大于背包的重量，因此我们无法将任何物品添加到背包中；因此，在 M[4][2] 中添加 0，如下所示：

当 i = 4，W = 3 时

值 4 对应的重量是 6，即 w₄ = 6。由于集合中有重量分别为 3、4、5 和 6 的四个物品，而背包的重量是 3。可以将重量为 3 的物品放入背包，其对应的利润为 2，因此在 M[4][3] 中添加 2，如下所示：

当 i = 4，W = 4 时

值 4 对应的重量是 6，即 w₄ = 6。由于集合中有重量分别为 3、4、5 和 6 的四个物品，而背包的重量是 4。可以将重量为 4 的物品放入背包，其对应的利润为 3，因此在 M[4][4] 中添加 3，如下所示：

当 i = 4，W = 5 时

值 4 对应的重量是 6，即 w₄ = 6。由于集合中有重量分别为 3、4、5 和 6 的四个物品，而背包的重量是 5。可以将重量为 4 的物品放入背包，其对应的利润为 3，因此在 M[4][5] 中添加 3，如下所示：

当 i = 4，W = 6 时

值 4 对应的重量是 6，即 w₄ = 6。由于集合中有重量分别为 3、4、5 和 6 的四个物品，而背包的重量是 6。在这种情况下，我们可以将重量为 3、4、5 或 6 的物品放入背包，但重量为 6 的物品的利润 (4) 是所有物品中最高的；因此，在 M[4][6] 中添加 4，如下所示：

当 i = 4，W = 7 时

值 4 对应的重量是 6，即 w₄ = 6。由于集合中有重量分别为 3、4、5 和 6 的四个物品，而背包的重量是 7。在这里，如果我们选择重量为 3 和 4 的两个物品，它们将产生最大利润，即 (2 + 3) = 5，因此在 M[4][7] 中添加 5，如下所示：

当 i = 4，W = 8 时

值 4 对应的重量是 6，即 w₄ = 6。由于集合中有重量分别为 3、4、5 和 6 的四个物品，而背包的重量是 8。在这里，如果我们选择重量为 3 和 4 的两个物品，它们将产生最大利润，即 (2 + 3) = 5，因此在 M[4][8] 中添加 5，如下所示：

正如我们在上面的表格中所观察到的，5 是所有条目中的最大利润。指针指向最后一个行和最后一个列，其中包含 5。现在我们将 5 与上一行进行比较；如果上一行，即 i = 3，包含相同的 5，则指针将向上移动。由于上一行包含 5，因此指针将向上移动，如下表所示：

我们再次将值 5 与上一行，即 i = 2，进行比较。由于上一行包含 5，因此指针将再次向上移动，如下表所示：

我们再次将值 5 与上一行，即 i = 1，进行比较。由于上一行不包含相同的值，因此我们将考虑 i=1 行，并且与该行对应的重量是 4。因此，我们选择了重量 4，并拒绝了重量 5 和 6，如下所示：

x = { 1, 0, 0}

与该重量对应的利润是 3。因此，剩余利润为 (5 - 3) = 2。现在我们将此值 2 与行 i = 2 进行比较。由于行 (i = 1) 包含值 2；因此，指针向上移动，如下所示：

我们再次将值 2 与上一行，即 i = 1，进行比较。由于 i =0 行不包含值 2，因此将选择 i = 1 行，并且 i = 1 对应的重量是 3，如下所示：

X = {1, 1, 0, 0}

与该重量对应的利润是 2。因此，剩余利润为 0。我们将 0 与上一行进行比较。由于上一行包含 0 值，但该行的利润为 0。在此问题中，选择了两个重量，即 3 和 4，以最大化利润。