朴素算法

思路

每次例举第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优化，都是对代码做等价变形，只能在空间上优化