朴素算法
思路
每次例举第i个物品在体积为j的限制下选或者不选,保存能够达到的最大的组合,不选即是除掉第i个物品在相同体积下的最大值,选,即是除掉第i个物品和第i个物品的体积在相同体积下i-1个物品价值,最后求一个最大值。
时间复杂度$O(n^2)$
pyhon 代码
n,v=map(int,input().split())
sum=[]
for i in range(n):
sum.append([int(i) for i in input().split()])
# 初始化,先全部赋值为0,这样至少体积为0或者不选任何物品的时候是满足要求
f=[[0 for i in range(v+1)] for j in range(n+1)]
#每次例举第i个物品在体积为j的限制下选或者不选,保存能够达到的最大的组合
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]):# 判断背包容量是不是大于第i件物品的体积
# 在选和不选的情况中选出最大值
#1到i中选总体积小于等于j,1到i-1中选总体积小于等于j-vi,
#这里的i-1是因为sum从0开始存的,这里的i是从1开始存的,因此i要减去1才能和sum里面的数对应
f[i][j]=max(f[i][j],f[i-1][j-sum[i-1][0]]+sum[i-1][1])
print(f[n][v])
dp优化,都是对代码做等价变形,只能在空间上优化