详细解释 如何降到一维dp

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

8

二维dp 模拟

i = 1 时， dp[i] = {0,2,2,2,2,2}

i = 2 时， dp[2] = {0,2,4,6,6,6}

解释
i = 2
j = 1 $dp[2][1] = dp[i - 1][j]$
j = 2 $dp[2][2] = max(dp[1][2], dp[1][0] + v[i])$
j = 3 $dp[2][3] = max(dp[1][3], dp[ 1][1] + v[i])$
j = 4 $dp[2][4] = max(dp[1][4], dp[1][2] + v[i])$
j = 5 $dp[2][5] = max(dp[1][5], dp[1][3] + v[i])$

显然， $dp[i][1 … m]$ 的值 与$dp[i - 1][0 … m]$ 有关
所以
用 $pre[n]来保存 dp[i - 1][0 … m]$
用 $next[n] 来保存 dp[i][0 … m]$

更好一点的方法就是用一个数组

从解释中可以看出 $dp[2][3] = max(dp[1][2], dp[1][0] + v[1])$
也就是说$dp[大] 会用到 dp[小]$

如果先计算$dp[小] 会导致计算 dp[大] 时 用到的dp[小] 不再是 dp[i - 1] 的值 而是 dp[i] 的值$

这里重点解释一下 $为什么 dp[小] 不是 dp[i - 1] 的值 而是 dp[i] 的值$
当 i = 2时
dp[i-1] = {0,2,2,2,2,2}

j = 1 dp[i] = {0,2,2,2,2,2}
j = 2 dp[i] = {0,2,4,2,2,2} 注意 此时 $dp[i][2]的值 由 2 变成了 4$
j = 3 dp[i] = {0,2,4,6,2,2} 注意此时$dp[i][3]的值由2变成6$
j = 4 dp[i] = {0,2,4,6,2,2} 注意此时$dp[i][4] 需要用到dp[i - 1][2]的值$

如果采用一个数组的话$dp[i][4] 需要用到dp[i][2]的值$
$但是dp[i][2]的值已经在j = 2的时候更改了$

所以这里必须采用从大到小计算

因为 $dp[小] 不会用到dp[大]$

#include<iostream>

using namespace std;

int dp[1005];

int main(){
    int n,m;
    cin >> n >> m;
    int v,w;

    //遍历前i个物品
    for (int i = 1; i <= n; i ++ ) {
        //从大到小 遍历体积
        cin >> v >> w;
        for (int j = m; j >= v; j -- ) {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }
    cout << dp[m] <<endl;
    return 0;

}