一般用动态规划(DP)。
每件物品只能选一次。
def bag_01(V, W, carry, N):
res = [0] * (carry+1)
for i in range(N):
for j in range(carry, W[i]-1, -1):
res[j] = max(res[j], res[j-W[i]]+V[i])
return res[-1]
每件物品可以选无数次。
完全背包的特点恰是每种物品可选无限件,所以就可以并且必须采用 w = W[i]…carry 的顺序循环:
def bag_absolute(V, W, carry, N):
res = [0] * (carry+1)
for i in range(N):
for j in range(W[i], carry+1): # 这是和01背包唯一的区别:正序遍历
res[j] = max(res[j], res[j-W[i]]+V[i])
return res[-1]