给定 n 种物品和一背包。物品 i 的重量是 $w_i$，其价值为$v_i$ ，背包的容量为 C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 对于一种物品，要么装入背包，要么不装。
解法一：暴力递归
可能性分析：
f ( i, rest ) 物品 i ，背包容量为 rest 时，能装入的物品的最大总价值。
- 物品 i 放入背包：res1 = f( i + 1, rest - w[i] )
- 物品 i 不放入背包：res2 = f( i + 1, rest )
- 决策：res = max( res1, res2 )
算法模型：从左向右依次对每个元素进行尝试（保留或者丢弃），根据最大值决策。
01背包问题，可能性尝试题里已经明确说明了（放入背包或者丢弃），也有很多其他题，需要自己从题的隐含条件中找到尝试的可能性。
这里的可能性只有两种，也有一些题需要遍历所有可能后（一次递归调用），再决策。
def knapsack01_v1(v, w, C):
return process1(v, w, 0, C)
def process1(v, w, index, rest):
if rest < 0: return -1
if index == len(w): return 0
p1 = process1(v, w, index + 1, rest)
p2 = 0
n = process1(v, w, index + 1, rest - w[index])
if n != -1:
p2 = v[index] + n
return max(p1, p2)
# 代码优化
def knapsack01_v2(v, w, C):
return process2(v, w, 0, C)
def process2(v, w, index, rest):
if index == len(w): return 0
return max(process2(v, w, index + 1, rest),
process2(v, w, index + 1, rest - w[index]) + v[index] if rest >= w[index] else 0)
解法二：动态规划
row 是 index
col 是 rest
可以从下向上填满矩阵也可以从上向下填满矩阵
def knapsack01_v2(v, w, C):
n = len(w)
dp = [[0] * (C + 1) for _ in range(n + 1)]
for row in range(n - 1, -1, -1):
for col in range(1, C + 1):
dp[row][col] = max(dp[row + 1][col], dp[row + 1][col - w[row]] + v[row] if col >= w[row] else 0)
return dp[0][C]
解法三：动态规划：滚动数组
根据上图，当前数据 f(i,rest) 只依赖下边临近的一行的数据，所以不需要一个完整的矩阵，需要保存一行数据，进行滚动更新。
注意：滚动更新的方向，只能从右向左。因为 i 行依赖 i + 1 行左边的数据，如果从左向右滚动更新 dp 数组，i 的 rest 之前的数据已经是新数据，没有办法用于后续的滚动更新了def knapsack01_v4(v, w, C):
n = len(w)
dp = [0] * (C + 1)
for row in range(n - 1, -1, -1):
for col in range(C, -1, -1):
dp[col] = max(dp[col], dp[col - w[row]] + v[row] if col >= w[row] else 0)
return dp[C]
def knapsack01_v5(v, w, C):
n = len(w)
dp = [0] * (C + 1)
for row in range(n):
for col in range(C, -1, -1):
dp[col] = max(dp[col], dp[col - w[row]] + v[row] if col >= w[row] else 0)
return dp[C]
对数器
import random
def generator_random_array(max_value, size):
return [int(random.random() * max_value) + 1 for _ in range(size)]
def check():
max_value = 10
max_size = 10
for i in range(500):
size = int(random.random() * max_size)
w = generator_random_array(max_value, size)
c = int(random.random() * sum(w))
v = generator_random_array(max_value, size)
res1 = knapsack01_v1(w, v, c)
res2 = knapsack01_v2(w, v, c)
res3 = knapsack01_v3(w, v, c)
res4 = knapsack01_v4(w, v, c)
if res1 != res2 or res1 != res3 or res1 != res4:
print("ERROR", res1, res2, res3, res4, w, v, c)
print("OVER!")
check()