通过这个问题开始对DP算法进行学习
个人的理解就是只归不递
想要v时大,就要v-1时大,想要v-1时大,就要…
首先将问题分为两个角度

状态表示

$f(i,j)$
i 表示了前i个物品
而j是其中的一个限制维度

表示了什么集合?

所有只考虑前i个物品,且总体积不超过j的选法的集合

具有什么属性?

集合中的最大值

状态计算

划分方法需要做到:不重复,不遗漏
本题可以以j为界
一边为所有不选择第i个物品的方案:即$f(i-1,j)$
另一边为选择第i个物品的方案:变化的部分为前面的选择,不变的为现在加上了i.所以想让全部的价值最大,应该为让前面变化的部分价值最大
那我们就对前面的部分进行进一步分析.
首先$V_总 <= j$ 那也就是说
$$
V_前 <= j-V_i
$$
那么我们就知道了子问题所考虑个数和限制条件,即求$f(i-1,j-v_i)$,最后加上$w_i$就是总的最大值了.
最后两个方案取最大

最终代码

1
2
3
4
5
6
7
8
9
10
11
n,v = map(int,input().split())
grid = []
for _ in range(n):
    grid.append(list(map(int,input().split())))
f = [[0 for _ in range(v+1)] for _ 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]#方案1
        if j >= grid[i-1][0]:#被减数大于减数
            f[i][j] = max(f[i][j],f[i-1][j-grid[i-1][0]]+grid[i-1][1])
print(f[n][v])