01背包的一维解法

从二维优化到一维后，背包容量 j 从大到小枚举，为什么呢？
在下面代码里的状态转移方程中，max()里的f[j]与等式左边的f[j]是不同的，前者是第i-1层的f[j]，后者是本层(第i层)待求的f[j]，同样的，f[j - v[i]]也是第i-1的状态，DP的思路是要用上一层的状态来更新这一层的状态。

（1）所以，如果j从小到大枚举：j = 1,…,m ，又因为j-v[i] < j，所以在本层（第i层）中f[j-v[i]] 肯定会在f[j]之前被计算出来。因此在下面的状态转移方程
f[j] = max(f[j], f[j-v[i]] + w[i])中，f[j-v[i]]是本层的状态，上一层的f[j-v[i]]被覆盖了，因此不是用上一层的状态来更新的f[j]，所以得不到正确结果。

（2）当j从大到小枚举：j = m,…,1，由 j-v[i] < j，所以f[j]的计算是在 f[j-v[i]] 之前完成的，因此在
更新f[j]的状态时，f[j-v[i]]还保留着上一层(第i-1层)的状态，因此可以得到正确结果。

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;

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

int main()
{
    int n,m;
    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--)
            f[j] = max(f[j],f[j-v[i]] + w[i]);


    cout<<f[m];
    return 0;
}

01背包的二维解法

#include<iostream>
using namespace std;

const int N = 1010;

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

int main()
{
    int n,m;
    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++)
        {
            f[i][j] = f[i-1][j]; //不放第i个物品，背包容量为j，所能获得的最大价值。
            if(j >= v[i])
            {
                f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]); //第二项表示在能放下第i个物品的情况下，放第i个物品，所能获得的最大价值
            }
        }
    cout<<f[n][m];
    return 0;
}