完全背包问题(python)
思路
01背包和完全背包最大的不同在于01背包只考虑一个物品选还是不选只有两种情况,完全背包需要考虑一个物品需要选几次,1,2,3,4,5,6.....然后再,把得到的等式做一个优化,把j换成v-j可以发现,j的等式后面一串等于v-j后面一串再加一个w
python 代码 $O(n^2)$
n,v=map(int,input().split())
sum=[]
for i in range(n):#存几个数
sum.append([int(j) for j in input().split()])#把每一个数都强制转换成int类型,并从0开始存
f=[[0 for i in range(v+1)] for j in range(n+1)]
for i in range(1,n+1):
for j in range(1,v+1):
f[i][j]=f[i-1][j]
if(j>=sum[i-1][0]):#sum里面的i需要减一是因为,i从1开始,而sum里面的i从0开始,不减一,数组下标会越界
f[i][j]=max(f[i][j],f[i][j-sum[i-1][0]]+sum[i-1][1])
print(f[n][v])