01背包问题

描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi 用空格隔开，分别表示第 ii 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000
0<vi,wi≤1000

思路

首先找状态转移方程，有两个变量物品数量和背包容积，则 i 表示物品号，j 表示背包容积。

f[i][j] 表示只看前i个物品，总体积是j的情况下，总价值最大是多少
// 注意是只看，不是装了多少物品

result = max(f[n][e-v])

f[i][j]:
1. 不选第i个物品： f[i][j] = f[i-1][j]; //直接等于只看上i个物品得到的结果
2. 选第i个物品： f[i][j] = f[i-1][j-v[i]];

每次循环的赋值：
f[i][j] = max{1., 2.}

初始化：
f[0][0] = 0;

代码

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

using namespace std;

const int N = 1010;

int n, m;
int f[N][N];
int v[N], w[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++) {
            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]); //选了i，则要加w[i]
            }
        }
    }

    int res = 0;

    for ( int i=0; i<=m; i++ ) res = max(f[n][i],res);

    cout << res <<endl;

    return 0;
}

优化思路

由两层循环中来看主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。

那么，如果只用一个数组f [0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？

f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v -c[i]]的值呢？

事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i -1][v-c[i]]的值。

伪代码如下：

for i=1..N
for v=V..0 //逆序
f[v]=max{f[v],f[v-c[i]]+w[i]};

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]。

推知，与本题意不符，但它却是另一个重要的背包问题完全背包问题最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。

同时，最后结果也可以转化为res = f[m]

    初始化的时候所有f[max]都等于0
    fin_k < m;

    f[fin_k] = max_w;
    f[0] = 0 => f[v[0]] = w[0] => ...

    f[m -k] = 0 => f[m - k + v[0]] = w[0] => ... //之后的可以枚举到之前的状态

如果要记录每次看前i个值得到的最大f[i]，则初始化的时候需要只将f[0]设置为0，其它设置为负最大值:

        f[0] = 0;
    f[i] = -INF;

优化后代码

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

using namespace std;

const int N = 1010;

int n, m;
int f[N];
int v[N], w[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 = m; j>=v[i]; j--) {
                f[j] = max( f[j], f[j - v[i]] + w[i]);
                      //每次f[j]更新都用到之前i-1时候留下来的f[j](实际上是f[i-1][j])
        }
    }


    int res = f[m];
    cout << res <<endl;

    return 0;
}

---