题目描述

01背包本质，以及依托于状态转移表格的一维优化

C++ 代码

//2021.4.19
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int n,m;
const int N=1010;

int f[N][N];
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++)
    {
        for(int j=0;j<=m;j++)//为啥只能从零开始？,不，应该是为啥必须从零或1开始
        //本质上还是画一个表格明白背包问题更新最优解的过程，你会发现，你惯性思维j从v[i]开始免去循环是不对的
        //这样做使得不能装本件物品的背包连原本可以继承上一个状态的本领也没有了，从比如2变成了0.肯定是不对的
        {
            f[i][j]=f[i-1][j];
            if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][m];

    return 0;
}

//简化为一维度的写法,一维优化你要明白f数组只是个记录结果的东西，所以我们不必保留状态转移的中间结果
//改写成一维需要注意，根据二维转移方程，新的结果必须从上一行i转移而来，也就是必须是旧的，不能是本轮循环新带来的
//所以可以倒立着来进行状态转移，还有个小困惑那第一行倒着来怎么办，一想第一行代表第一个物品的抉择，无论正反都不带来第一行状态的改变
/*int main()
{
    cin>>n>>m;

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

    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)//为啥改成一维度又这样写了？还是去想整个更新的过程，这里v[i]就可以，因为会默认保留你懂吗宝贝
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];

    return 0;
}*/

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla