二维DP

闫氏DP分析法

图示：

状态计算： f[i][j] 表示所有从前i个物品选，且总体积不超过j的选法集合中的价值最大值

那么f[n][m]就表示从前n种物品中选，且总体积不超过为m的所有选法集合的价值最大值，即为答案。

集合划分：

按照第i种物品选或者不选划分 f[i][j]集合。

不选第i种物品,f[i][j] = f[i-1][j];
问题转化为从前i-1个物品选，且总体积不超过j的选法集合中的最大值。

选第i种物品, f[i][j] = f[i-1][j-v] + v*w ;
已经确定选第i种物品，那么问题转化为从前i-1个物品选，且总体积不超过j-v的选法集合中的最大值再加上 v*w。

状态计算方程：

ac代码：

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 3e4 + 10,M = 30;
int v[M], w[M];
int f[M][N];
int n, m;
int main() {
    cin >> m >> n;
    for(int i = 1; i <= n; i++)  cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i++) 
    {
        for(int j = 0; j <= m; j++) 
        {
            f[i][j] = f[i-1][j];
            if(j>=v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]]+v[i]*w[i]);
        }
    }
    cout << f[n][m] << endl;
 return 0;    
}

一维DP

考虑优化

状态计算时f[i]层的更新只用到了f[i-1]层,我们去掉前一维

状态计算方程为 ：f[j] = max(f[j], f[j-v]+v*w);

代码表示：

for(int j = v[i]; j <= m; j++) 
{
   f[j] = max(f[j], f[j-v[i]]+v[i]*w[i]);
}

此时不和之前的代码等价了，因为在计算第i层的状态时，我们从小到大枚举体积，体积 j-v[i]严格小于j,那么f[j-v[i]]会先于f[j]被计算出来，此时我们计算出来的f[j-v[i]]仍为第i层状态，这样f[j-v[i]]等价于f[i][j-v[i]] ,实际上f[j-v[i]]应该等价于f[i-1][j-v[i]]。

为了解决这个问题只需要体积从大到小枚举，

for(int j = m ; j >= v[i]; j--) 
{
   f[j] = max(f[j], f[j-v[i]]+v[i]*w[i]); 
}

因为我们从大到小枚举体积，而 j - v[j]严格小于j,我们在计算f[j] 的时候f[j-v[i]]还未被第i层状态更新过，那么它存的就是上一层(i-1层)的状态，即f[i-1][j-v[i]]。

ac代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3e5 + 10;

int n, m;
int f[N];

int main()
{
    cin >> m >> n;

    for (int i = 0; i < n; i ++ )
    {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j -- )  //体积从大往小枚举
            f[j] = max(f[j], f[j - v] + w*v);
    }
    cout << f[m] << endl;

    return 0;
}