通过这个问题开始对DP算法进行学习

个人的理解就是只归不纳，想要v时大,就要v-1时大,想要v-1时大,就要…

首先将问题分为两个角度：

状态表示

$f(i,j)$

i 表示了前i个物品，而j是其中的一个限制维度。

表示了什么集合？

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

具有什么属性？

集合中的最大值。

状态计算

划分方法需要做到：不重复，不遗漏

本题可以以j为界

一边为所有不选择第i个物品的方案：$f(i-1,j)$

另一边为选择第i个物品的方案:变化的部分为前面的选择,不变的为现在加上了i.所以想让全部的价值最大,应该为让前面变化的部分价值最大,那我们就对前面的部分进行进一步分析。

首先$V_1+V_2+…+V_{i-1}<= j$ 那也就是：
$$
V_1+V_2+…+V_{i-1}<= 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])