背包九讲1——01背包

题目

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

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

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

输入格式

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

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

输出格式

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

数据范围

$0<N,V≤1000$
$0<v_i,w_i≤1000$

朴素方法：二维数组

我们使用二维数组 $f[i][j]$ ，表示前 $i$ 个物品放入空间为 $j$ 的背包中所能得到的最大价值。

因为每个物品只能选一次，所以对于物品 $i$ 且背包容量为 $j$ 的情况，我们有以下两种选择：

1. 不选，此时最大价值等于前 $i-1$ 件物品的最大价值。

   $f[i][j]=f[i-1][j]$

2. 选，此时最大价值等于前 $i-1$ 件物品且背包容量为 $j-v[i]$ 时的最大价值。

   $f[i][j] = f[i-1][j-v[i]]+w[i]$

两者取最大即可。

最终结果取 $f[n][m]$ 即可。

初始化： $f[0][j]$ 和 $f[i][0]$ 初始化为 $0$。

复杂度： 时间复杂度 $O(NV)$ ，空间复杂度 $O(NV)$

#include <bits/stdc++.h>
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];
    }
    // 01背包
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; 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]);
            }
        }
    }
    
    cout << f[n][m] << endl;
    
    return 0;
}

空间优化：一维数组

由于每一层的状态只与上一层有关，所以我们可以采用滚动数组来优化空间：

$f[j]$ 表示背包容量为 $j$ 时最大的价值。

$f[j] = max(f[j],f[j-v[i]])$

具体做法是：从 $1…N$ 顺序遍历物体，第二层循环我们需要逆向遍历，如上式，等号左边是要求的前 $i$ 件物品的价值，而等号右边是前 $i-1$ 件物品的价值，逆序遍历保证了等号右边的数值是未更新的。

初始化： $f[0…V]=0$ ，若题目要求恰好装满背包，则 $f[0]=0, f[1..V] = -\infty$ ，这样保证了所有合法结果都是从 $f[0]$ 转移过来的，最后判断一下 $f[V]$ 是否合法即可。

复杂度： 时间复杂度 $O(NV)$ ，空间复杂度 $O(V)$

#include <bits/stdc++.h>
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]);
        }
    }
    cout << f[m] << endl;
    
    return 0;
}