基于y氏dp法分析01背包问题并优化

原题链接

不多说，直接上图，我相信acwing的学员应该都秒懂吧

那么，集合划分完了，又该如何进行计算呢？

• 不包含i：很简单，直接f(i-1,j)就行了
• 包含i：直接算比较困难，用一招曲线救国

我们是一定知道f(i-1,j)的情况的
现在的想法是，如果能求出前i-1选法的最大值，那么加上这个物品，仍然是当前状态的最大值

这个状态可以表示为f(i-1,j-v)+w

其中v代表当前物品的体积，w代表当前物品的价值

这样算就一定能保证选到第i个物品，并且求的是最大值

那么f(i,j)的最大值，就是这两种选法的最大值
这是个二维dp问题，所以是双重循环

细节问题见代码注释

代码实现：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n,m;//n表示有N个物品，m表示背包体积为M
int v[N],w[N];
int f[N][N];

int main()
{
    cin>>n>>m;
    for (int i = 1; i <= n; i ++ ) cin>>v[i]>>w[i];

    //前0个物品总价值一定是0，所以f[0][?]一定是0，但全局变量已经初始化了，所以这里不考虑
    for (int i = 1; i <= n; i ++ )
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];//这是不考虑第i个物品的情况
            //考虑第i个物品的话，首先考虑背包还能不能放下
            //能放下才能考虑这个情况
            if(j>=v[i])
            {
                f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
                //先算去掉第i个物品的最大值
                //f[i-1][j-v[i]]
                //然后再加上第i个物品的价值w[i]
            }
        }
    }
    cout<<f[n][m]<<endl;//最后状态就是我们要的答案
    return 0;
}

优化为一维状态

我们首先观察我们的状态转移

f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i](如果存在));

我们发现，f[i][j]依赖的状态值永远为上一层[i-1]的状态

所以我们可以利用滚动数组进行优化
首先假设当前的一维数组已经存储了当前状态的上一层状态的值
我们可以从后往前计算，这样不会有数据覆盖问题，也能达到题目要求

更多细节问题参见代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int f[N];

int main()
{
    cin>>n>>m;
    for (int i = 1; i <= n; i ++ ) cin>>v[i]>>w[i];

    for (int i = 1; i <= n; i ++ )
    {
        //从后往前遍历防止当前层数据的数据覆盖
        //遍历结束条件是j>=v[i]是因为要满足背包容量问题
        //在计算前，当前数组保留的还是上一层数据
        //所以max中的f[j]其实等价于f[i-1][j]
        for (int j = m; j >= v[i]; j -- )
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;
    return 0;
}