从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)大小，第一行和第一列始终为0valueSum = [[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# 输出# 30N = 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. 完全背包问题参考博客

原著是一个有趣的人,若有侵权,请通知删除