背包问题
问题描述
有N件物品和一个容量为C的背包。第i件物品的体积是w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。
状态转移矩阵：
mem[i][j] = max(mem[i-1][j], mem[i-1][j - w[i-1]] + v[i-1])
即，拿该件物品时的价值，与不拿该件物品（即mem[i-1][j]）时的价值，取最大值
当要拿的物品重量大于背包容量时，无论如何都不能拿这件物品，则
mem[i][j]=mem[i-1][j]
状态矩阵
def knapsack(w, v, C):
# mem[i][j]即对应可能拿i件物品（只能是前i件，其中这些可以拿，也可以不拿）
# 背包容量为j对应的最大价值
mem = [[0 for _ in range(C + 1)] for _ in range(len(w) + 1)]
# 填充数组，注意第 0 行和第 0 列都不管
for i in range(1, len(w) + 1):
for j in range(1, C + 1):
if w[i - 1] <= j: # 要拿的物品体积小于背包容量
mem[i][j] = max(mem[i - 1][j],
mem[i - 1][j - w[i - 1]] + v[i - 1])
else: # 物品容量大于背包容量，则 mem[i][j] 等于不拿该物品
mem[i][j] = mem[i - 1][j]
v = [8, 10, 6, 3, 7, 2]
w = [4, 6, 2, 2, 5, 1]
print(knapsack(w, v, 12))
