从01背包到完全背包

01背包python代码（对应参考资料1练习题）

N = int(input())
V = int(input())

value = list()
value.append(0)
volume = list()
volume.append(0)
for i in map(int, input().split()):
    volume.append(i)
for i in map(int, input().split()):
    value.append(i)
# 初始化表，(N+1)*(V+1)大小，第一行和第一列始终为0
valueSum = [[0 for col in range(V+1)] for row in range(N+1)]
for v in range(1, V+1):
    for k in range(1, N+1):
        if volume[k] > v:
            valueSum[k][v] = valueSum[k-1][v]
        else:
            valueSum[k][v] = max(valueSum[k-1][v], valueSum[k-1][v-volume[k]] + value[k])

print(valueSum[N][V])

01背包问题对于每种物品有两种选择，取或者不取（1或0），故而叫01背包，01背包问题中每种物品只能选一次。而完全背包就有点不同，在完全背包问题中，每种物品可以选择任意多次
完全背包问题代码和01背包相比只多了层循环，这是因为01背包问题在第K个物品时只有选或不选两种选择，而完全背包问题，有多次选择（有限个数<=背包容量）
完全背包python代码

# 测试样例
# 输出
# 5
# 10
# 2 2 6 5 4
# 6 3 5 4 6
# 输出
# 30
N = int(input())
V = int(input())

value = list()
value.append(0)
volume = list()
volume.append(0)
for i in map(int, input().split()):
    volume.append(i)
for i in map(int, input().split()):
    value.append(i)
valueSum = [[0 for col in range(V+1)] for row in range(N+1)]
for v in range(1, V+1):
    for k in range(1, N+1):
        for i in range(int(v/volume[k]) + 1):
            valueSum[k][v] = max(valueSum[k][v], valueSum[k-1][v-volume[k]*i] + i*value[k])

print(valueSum[N][V])

参考资料

1. 牛客网01背包练习题
2. 完全背包问题参考博客