共计 1774 个字符，预计需要花费 5 分钟才能阅读完成。
01 背包问题
有 n 个物品，1 个容量 v 的背包，第 i 个物品体积是 volume[i]，价值是 value[i]，问将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大，每个物品只能应用 1 次。
思考中间状态，有 i 个物品，有 j 个容量，该状态的最高价值为 status[i][j]。该状态能够由其上一个状态转移取得，对于第 i 个物品，咱们能够将其抛弃或放入背包，取两者最大值。
抛弃：status[i][j] = status[i-1][j]
放入：status[i][j] = value[i] + status[i-1][j-volume[i]]
这里的（i，j）状态，是第 i 个物品曾经做出抉择的后果，他须要上一个状态即抉择第 i - 1 个物品后的后果转移而来。j – volume[i] 能够了解为，抉择物品 i 后的容量是 j，那么未抉择之前为 j – volume[i]。
def solution(n, v, volume, value):
status = [[0]*(v+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, v+1):
if j - volume[i-1] >= 0:
status[i][j] = max(status[i-1][j], value[i-1] + status[i-1][j-volume[i-1]])
else: status[i][j] = status[i-1][j]
return status[n][v]对于矩阵 status，其状态只在 i - 1 和 i 两行之间转移，咱们能够应用滚动数组也就是只用两行来一直地更新，保护上一步和以后步的状态，以达到升高空间复杂度的目标。
这里应用状态压缩，只用一行来记录状态，将二维 DP 降到一维 DP。将下面的代码稍作改变，能够失去上面的错误代码，这里只是单纯的把 i 状态删掉了。尽管是谬误的代码，但咱们须要它来辅助了解。
def solution(n, v, volume, value):
status = [0]*(v+1)
for i in range(1, n+1):
for j in range(1，v+1):
if j - volume[i-1] >= 0:
status[j] = max(status[j], value[i-1] + status[j-volume[i-1]])
else: status[j] = status[j]
return status[v]该段代码的问题在于，对于 status[j] 的计算须要依赖于 status[j-volume[i]] 的后果，在二维中，status[j] 和 status[j-volume[i]] 是别离处于不同行的，也就是 i 与 i - 1 两行，然而在一维中，它们都在同一行。
并且 j 值是向右增长的，也就是说在计算 status[j] 时，status[j-volume[i]] 的值早已被更新为第 i 行的状态了，而不是上一步的状态。所以咱们须要让 j 值向左增长。失去如下代码。
def solution(n, v, volume, value):
status = [0]*(v+1)
for i in range(1, n+1):
for j in range(v, 0, -1):
if j - volume[i-1] >= 0:
status[j] = max(status[j], value[i-1] + status[j-volume[i-1]])
else: status[j] = status[j]
return status[v]这段代码曾经是正确的了，然而还不够完满，察看后不难发现 status[j] = status[j] 这一步是齐全没有必要存在的，因而咱们能够管制 j 的最小值，保障 j – volume[i-1] >= 0 成立。失去最终代码如下。
def solution(n, v, volume, value):
status = [0]*(v+1)
for i in range(1, n+1):
for j in range(v, volume[i-1]-1, -1):
status[j] = max(status[j], value[i-1] + status[j-volume[i-1]])
return status[v]之所以该问题被称作 01 背包，其起因在于对于每一样物品只能应用一次。在咱们遇到的题目中，往往是 01 背包问题的变体，咱们须要学会如何将题目转换为经典的 01 背包问题。
相干题目：宰割等和子集、一和零、最初一块石头的分量 II。
