0-1 背包问题

假设你被问到，考虑到你可以随身携带背包的总重量以及一些带有重量和价值的物品，你怎么能以这样的方式取出这些物品，使得它们的价值总和最大，但是它们的重量总和不是超过你可以携带的总重量？在 0-1 指示任你挑选的项目，或者你没有。我们每个项目都有一个数量。这意味着，你无法拆分该项目。如果它不是 0-1 背包问题，那意味着如果你可以拆分项目，那就有一个贪婪的解决方案，这称为分数背包问题。

现在，让我们专注于手头的问题。例如，假设我们的背包容量为 7 。我们有 4 个项目。他们的权重和值是：

+----------+---+---+---+---+
|   Item   | 1 | 2 | 3 | 4 |
+----------+---+---+---+---+
|  Weight  | 1 | 3 | 4 | 5 |
+----------+---+---+---+---+
|   Value  | 1 | 4 | 5 | 7 |
+----------+---+---+---+---+

一种蛮力方法将采用所有可能的项目组合。然后我们可以计算出它们的总重量，并将它们排除在超出我们背包容量的范围内，并找出能给我们带来最大价值的那个。对于 4 个项目，我们需要检查（ 4！ - 1 ）= 23 种可能的组合（不包括没有项目的组合）。当项目数量增加时，这非常麻烦。在这里，我们可以注意到的几个方面，即：

• 我们可以使用较少的项目并计算使用这些项目可以获得的最大值并将它们组合起来。所以我们的问题可以分为子问题。
• 如果我们计算项 {1,2} 的组合，我们可以在计算 { 1,2,3} 时使用它。
• 如果我们最小化重量并使价值最大化，我们可以找到最佳解决方案。

出于这些原因，我们将使用动态编程来解决我们的问题。我们的策略是：每当有新商品出现时，我们会检查是否可以选择商品，我们会再次选择能够带来最大价值的商品。现在，如果我们选择项目，我们的价值将是项目的价值，加上我们可以通过从我们的产能中减去价值以及我们可以获得的剩余重量的最大值来获得的价值。如果我们不选择该项目，我们将选择能够在不包含该项目的情况下为我们提供最大价值的项目。让我们尝试用我们的例子来理解它：

我们将采用一个二维数组表，其中列数将是我们可以通过取项目+ 1 获得的最大值。行数将与项目数相同。我们的数组看起来像：

+-------+--------+---+---+---+---+---+---+---+---+
| `Value` | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

为方便起见，我们将每个项目的重量和价值合并到阵列中。请记住，这些不是数组的一部分，这些仅用于计算目的，你不需要将这些值存储在表数组中。

我们的第一列填充 0 。这意味着如果我们的最大容量为 0 ，无论我们拥有什么项目，因为我们无法选择任何项目，我们的最大值将为 0 。让我们从表[0] [1]开始。当我们填写表[1] [1]时，我们问自己我们的最大容量是否为 1 而我们只有第一项，我们的最大值是多少？我们所能做的最好的就是 1 ，选择项目。对于表[0] [2] ，这意味着如果我们的最大容量是 2 并且我们只有第一个项目，我们可以得到的最大值是 1 。对于表[0] [3] ，这将是相同的，表[0] [4] ，表[0] [5] ，表[0] [6] 和表[0] [7] 。这是因为我们只有一个项目，它给我们的价值 1 。由于我们每个项目只有 1 个数量，无论我们如何增加背包的容量，从一个项目， 1 是我们可以做出的最佳价值。所以我们的数组看起来像：

+-------+--------+---+---+---+---+---+---+---+---+
| `Value` | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

继续，对于表[1] [1] ，我们问自己，如果我们有第 1 项和第 2 项，如果背包的最大容量是 1 ，那么我们可以获得的最大值是多少？如果我们同时采用第 1 项和第 2 项，总重量将为 4 ，这将超过我们目前的背包容量。因此无法选择第 2 项。现在，如果不考虑第 2 项，我们能做的最好的事情是什么？从顶部开始的值，即 Table [0] [1] ，它包含我们可以获得的最大值，如果我们有最大容量 1 并且我们没有选择第二项。对于表[1] [2] ，因为 2 小于重量[2] ，即第二项的重量，我们不能拿该项。因此，我们可以确定，如果当前项目的权重大于我们的最大容量，我们就不能接受该项目。在这种情况下，我们只需从顶部取值，它代表我们可以采取的除项目之外的最大值。

if weight[i] > j
    Table[i][j] := Table[i-1][j]
end if

现在对于**表[1] [3]，**因为我们的最大容量等于我们当前的重量，我们有两个选择。

• 我们选择该项目并使用我们在获取此项目后可从其他剩余项目获得的最大值添加其值。
• 我们可以排除这个项目。

在这两个选择中，我们将选择一个可以获得最大价值的选择。如果我们选择项目，我们得到：此项目的值+取得此项目后其余项目的最大值= 4 + 0 = 4 。我们得到 4 从我们（的项目值） 重量阵列和 0 （我们可以从项目的其余部分采取这一项目后，获得最大价值）来通过去 1 个上面的步骤和 3 步回来。那是表[0] [0] 。为什么？如果我们采取该项目，我们的剩余容量将是 3 - 3 = 0 ，剩余项目将是第一项。好吧，如果你还记得表[0] [0] 存储我们可以获得的最大值，如果我们的容量为 0 并且我们只有第一项。现在，如果我们不选择项目，我们可以获得的最大值来自上面的 1 步，即 1 。现在，我们取最大值这两个值的（ 4 ， 1 ），并设置表[1] [2] = 4 。对于表[1] [4] ，从 4 开始，最大背包容量大于 3 ，即我们当前项目的重量，我们再次有两种选择。我们取 max（ Weight [2] + Table [0] [4-Weight [2]] ， Table [0] [4] ）= max（ 重量[2] +表[0] [1] ，表[0] [4] ）= MAX（ 4 + 1 ， 1 ）= 5 。

if weight[i] <= j
    w := weight[i]
    Table[i][j] := max(w + Table[i][j-w], Table[i-1][j])
end if

使用这两个公式，我们可以填充整个 Table 数组。我们的数组看起来像：

+-------+--------+---+---+---+---+---+---+---+---+
| `Value` | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+

这里，我们在数组中插入的最后一个值 Table [3] [7] 包含了我们所需的最大值。如果我们有 4 件物品，我们可以得到的最大值，背包的最大容量是 7 。

这里有一点我们必须记住，即使是第一排，重量也可能大于背包的容量。在填充第一行时，我们需要保留另一个约束来检查值。或者我们可以简单地取另一行并将第一行的所有值设置为 0 。伪代码看起来像：

Procedure Knapsack(Weight, Value, maxCapacity):
n := Item.size - 1
Table[n+1][maxCapacity+1]
for i from 0 to n
    Table[i][0] := 0
end for
for j from 1 to maxCapacity
    if j >= Weight[0]
        Table[0][j] := Weight[0]
    else
        Table[0][j] := 0
    end if
end for
for i from 1 to n
    for j from 1 to maxCapacity
        if Weight[i] >= j                                            //can't pick the item
            Table[i][j] := Table[i-1][j]        
        else                                                        //can pick the item
            w := Weight[i]
            Table[i][j] := max(w + Table[i-1][j-w], Table[i-1][j])
        end if
    end for
end for
Return Table[n][maxCapacity]

这个算法的时间复杂度是 O(n*maxCapacity)，其中 n 是项目数，maxCapacity 是我们背包的最大容量。

到目前为止，我们已经找到了我们从示例中获得的最大值。还有一个问题。什么是实际物品？我们将回溯 Table 数组中的值以找出我们采用的项目。我们将遵循两个策略：

• 对于任何项目，如果值来自上面的位置，我们没有采取当前项目。我们走了一步。
• 如果价值不是来自上面的位置，我们就拿走了这个项目。所以我们走上一步，x 退后一步，其中 x 是当前项目的权重。

伪代码将是：

Procedure printItems(Table, maxCapacity, Value):
i := Item.size - 1
j := maxCapacity
while j is not equal to 0
    if Table[i][j] is equal to Table[i-1][j]
        i := i - 1
    else
        Print: i
        j := j - weight[i]
        i := i - 1
    end if
end while

如果我们回顾我们的例子，我们将得到：

https://i.stack.imgur.com/UrImV.jpg

由此我们可以说，我们可以采取第 2 项和第 3 项来获得最大值。