0/1 Knapsack Problem
你有 n 件物品。第 i 件物品的重量为 weights[i]，价值为 values[i]。你的背包最多能装 capacity 重量的物品。每件物品只有一件，你要么将它整件装入背包，要么不装。返回你能装入背包的最大总价值。
函数
- weightsinteger-array
- 每个项目的权重
- valuesinteger-array
- 每个项目的值
- capacityinteger
- 背包最多能承载的重量
- 返回值integer
- 在不超过容量的情况下，物品的最大总价值
约束条件
1 ≤ n ≤ 100，其中n = weights.length = values.length1 ≤ weights[i] ≤ 10001 ≤ values[i] ≤ 1041 ≤ capacity ≤ 1000
示例
- 输入
- weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
- 输出
- 17
- 解释
- 物品 0 和 2 的重量为 4 + 3 = 7，价值为 10 + 7 = 17。先装入价值最高的物品（重量为 5，价值为 12）后，只剩下装入物品 1 的空间，总价值为 16。
- 输入
- weights = [5, 4, 3]values = [10, 7, 6]capacity = 7
- 输出
- 13
- 解释
- 物品 1 和 2 的重量为 4 + 3 = 7，价值为 7 + 6 = 13。物品 0 每单位重量可获得 2 的价值，与其他物品一样多，但选了它之后，剩下的 2 个单位放不下任何物品。
- 输入
- weights = [6, 8]values = [5, 9]capacity = 5
- 输出
- 0
- 解释
- 这两件物品的重量都超过 5，所以都装不进去，空背包的价值为 0。
进阶
假设容量可以达到 10^9，而数值总和最多为 10^4。你会用什么作为表的索引？
提示
逐个打开提示，每个都会多透露一点。
按顺序决定是否选择这些物品，从物品 0 开始。无论你选择它还是不选择它，接下来都要面对关于后续物品的同一个问题。这个问题中的哪个数字会变化？
从现在开始，最佳值只取决于两个数字：你正在查看哪个物品，以及还剩多少空间。有 100 个物品，容量为 1000，因此大约有 10^5 个这样的组合，你可以把每种组合计算一次并保存下来。
为从
0到capacity的每个容量c保留best[c]，初始时它们都为0。对于重量为w、价值为v的物品，让c从capacity递减到w，并保留best[c]和best[c-w] + v中较大的值。递减遍历可以防止同一件物品被装入两次。
题解
没有一种贪心顺序可行：在第一个示例中，先装价值最高的物品，结果是 16，而不是 17。从物品 i 开始能得到的最佳价值，只取决于 i 和剩余容量，容量是一个最大为 1000 的整数。每对组合对应一个表格单元格，复杂度为 O(n × capacity)；如果按容量从大到小遍历，只需一行。
尝试每个项目的两种选择
结果正确，但无法在最大的测试中运行完毕
思路
设 best(i, room) 表示从第 i 个物品开始，在有 room 单位剩余容量时能装入物品的最大价值；超过最后一个物品后，结果为 0。跳过物品 i 会得到 best(i+1, room)。如果 weights[i] ≤ room，装入它会得到 values[i] + best(i+1, room-weights[i])。取较大的值。每一种能装下的装法，都对应一串装入和跳过的选择，递归会尝试所有选择。
每个物品都会使路径数量翻倍。当 100 个物品都能一起装下时，比如每个物品的重量都是 10，背包容量为 1000，路径数量就是 2^100。
算法
- 编写
best(i, room)，当i超过最后一件物品时，返回 0。 - 将
skip设为best(i+1, room)。 - 如果
weights[i] > room，返回skip。 - 否则，返回
skip和values[i] + best(i+1, room-weights[i])中较大的值。 - 返回
best(0, capacity)。
def knapsack(weights, values, capacity):
n = len(weights)
# The most value items i, i+1, ... can add with room units of weight left
def best(i, room):
if i == n:
return 0
skip = best(i + 1, room)
if weights[i] > room:
return skip
take = values[i] + best(i + 1, room - weights[i])
return max(skip, take)
return best(0, capacity)按项目和容量填写表格
思路
递归会沿着许多路径到达同一对 (i, room)。这样的组合最多有 101 × 1001 个，约为 10^5 个，因此每个组合只计算一次。
令 best[i][c] 表示前 i 件物品放入容量为 c 的背包时能获得的最大值；第 0 行全为 0。对于重量为 w、价值为 v 的物品 i-1，不放入它时，结果为 best[i-1][c]；当 w ≤ c 时，放入它的结果为 best[i-1][c-w] + v。第 i 行只读取第 i-1 行，因此每件物品最多只会进入一个单元格一次。
在第一个示例中，物品 2（重量为 3，价值为 7）会把容量 7 对应的值提升到 best[2][4] + 7 = 17。随后，物品 3 只能得到 best[3][2] + 12 = 16，因此答案仍为 17。
算法
- 创建一个有 n+1 行、capacity+1 列的表，并将所有值设为 0。
- 对于从 1 到 n 的每一行
i，取w = weights[i-1]和v = values[i-1]。 - 对于每个容量
c，将best[i][c]设为best[i-1][c]。 - 如果
w ≤ c，并且best[i-1][c-w] + v更大，就改为存储它。 - 返回
best[n][capacity]。
def knapsack(weights, values, capacity):
n = len(weights)
# best[i][c]: the most value from the first i items within capacity c
best = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = weights[i - 1], values[i - 1]
for c in range(capacity + 1):
best[i][c] = best[i - 1][c] # leave item i-1 out
if w <= c and best[i - 1][c - w] + v > best[i][c]:
best[i][c] = best[i - 1][c - w] + v # put it in
return best[n][capacity]一行，容量逐渐递减
思路
第 i 行只需要第 i-1 行，因此只保留一行 best[c]，并逐个物品覆盖它。遍历方向决定答案是否正确。
如果从小到大遍历 c，best[c-w] 可能已经包含当前物品。假设一个物品的重量为 3、价值为 5，背包容量为 6，那么容量为 3 时价值为 5，接着容量为 6 时读取这个值，就会变成 10，也就是用了两个物品。从 capacity 向下遍历到 w 时，你读取的单元格位于要写入的单元格下方，并且会在之后才被覆盖，因此它仍保存着上一行的值。
物品可以无限次选取时，从小到大遍历才是正确的循环。这里的时间复杂度仍为 O(n × capacity)，内存占用则降为一行。
算法
- 创建一个包含
capacity + 1个元素且全部为 0 的best。 - 对于每个重量为
w、值为v的物品，让c从capacity递减到w。 - 如果
best[c-w] + v大于best[c]，就将它存入best[c]。 - 返回
best[capacity]。
def knapsack(weights, values, capacity):
# best[c]: the most value from the items seen so far within capacity c
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
# Walk the capacities downward so each item goes in at most once
for c in range(capacity, w - 1, -1):
if best[c - w] + v > best[c]:
best[c] = best[c - w] + v
return best[capacity]
易错点和边界情况
- 在单行版本中按容量递增遍历，会把同一件物品放入两次：一件重量为 3、价值为 5 的物品放入容量为 6 的背包，得分是 10，而不是 5。
- 使用一行
capacity个条目，而不是capacity + 1个条目。返回best[capacity-1]会遗漏恰好装满背包的情况，例如重量为 1 的物品放入容量为 1 的背包。 - 将初始条目设为负无穷。背包不一定要装满，因此每个条目都从 0 开始；如果设为负无穷，第三个示例会返回负无穷，而不是 0。
- 重量超过背包容量的物品必须跳过。在第三个示例中，Swift 中的闭区间
w...capacity会使程序停止运行，而 R 中的(w+1):(capacity+1)会倒序计数。
常见问题3
0/1 背包问题的时间复杂度是多少？
表格算法的时间复杂度为 O(n × capacity)，约需 10^5 步来处理 100 件物品和容量为 1000 的情况；单行版本的空间复杂度为 O(capacity)。这个界是伪多项式的：它随容量的数值增长，而不是随其位数增长。一般问题是 NP-hard。
为什么贪心算法不适用于 0/1 背包问题？
贪心规则永远不会撤销一个选择，即使选了某个物品后剩余的容量无法装入其他物品。容量为 7 时，重量为 5、价值为 10 的物品单位价值比最高，但重量为 4 和 3 的物品组合起来价值为 13。按单位价值比进行贪心选择只对分数背包问题最优，因为你可以拆分物品。
如何找出 0/1 背包问题选中了哪些物品？
保留完整的表，并从 best[n][capacity] 开始向回追溯。如果 best[i][c] 与 best[i-1][c] 不同，说明物品 i-1 已被装入，因此记录它，并从 c 中减去它的重量。否则，转到第 i-1 行，并保持 c 不变。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def knapsack(weights, values, capacity):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
weights = [4, 2, 3, 5] values = [10, 4, 7, 12] capacity = 7
预期输出
17