单背包问题的优化

1. 优化前的动态规划解法

#include <iostream>

using namespace std;

const int N = 1010;

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

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

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

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

    cout << f[n][m] << endl;

    return 0;
}

2. 优化思路

原来的状态矩阵维度为m * n,但我们可以发现，每一行在计算的时候都只用到它上一行的值，而且我们只需要最后一行最后一列的结果f[n][m],那么干脆就只留一行。

这样的话f[i][j] = f[i-1][j]这句话就可以去掉了，因为在原二维矩阵中，它起到将上一行的数据复制到下一行，当我们只留一行时，就没有复制行的必要了。

但是f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i])这句话有可能是复制上一行同一列的数据，也有可能根据上一行j - w[i]的列求这一行第j列的值，如果我们是从左到右求的话，也就是从第一列开始更新，那么当我们更新到第j列时，j前面的列就不是上一行的数据了，但是如果从后往前更新，因为我们只用到列序号比当前列小的数据，而这些列都没有被重新计算过，所以可以保证他们还是上一行遗留下来的数据。

所以优化的本质就是，通过前一行算后一行，变成通过前面的列算后面的列，因为我们只需要求f[n][m]

3，优化后的代码

#include <iostream>

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 >> w[i] >> v[i];

    for(int i = 1; i <= n; i++)
        for(int j = m; j >= w[i]; j--) 
                 //从后往前遍历,所以循环开始时j=m，每次进行j--操作
                 //循环结束条件改为j>=w[i],因为当j<w[i]时，在原二维矩阵中只是将上一行的数据复制到下一行
                 //当只用一行矩阵时，这个操作就可以省略了
            f[j] = max(f[j], f[j-w[i]] + v[i]);

    cout << f[m] << endl;

    return 0;
}