思路
一般用动态规划（DP）。
输入参数
- W:各个物品的重量；
- V:各个物品的价值；
- carry:最大承重为carry的背包；
- N：物品件数。
0-1背包
代码语言：javascript复制每件物品只能选一次。
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 的顺序循环：
代码语言：javascript复制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]
