背包问题之01背包 全详解（最浅显易懂）

01背包是一种非常经典的动态规划问题，这里对01背包问题进行详细解读。

01背包问题题目描述

有 $N$ 件物品和一个容量为 $V$ 的背包。第$i$件物品的体积是 $c[i]$ ，价值是 $w[i]$ ，求将哪些物品装入背包可使价值总和最大。

01背包问题解析

对于所有的动态规划问题，第一步都是确定状态。我们定义状态 $dp[i][j]$ 是表示目前正在枚举第 $i$ 个物品，目前已取的总体积为 $j$，最大价值为$dp[i][j]$。
第二步自然是找状态转移方程。
首先我们注意一点：物品只有取和不取两种选择，这是符合我们日常生活的。状态转移方程就需要从这里为突破口来思考：
(1)：假如我们不取这个物品，那么 $dp[i][j]$ 肯定是能从上一个物品，同样体积转移过来的，所以 $dp[i][j]=dp[i-1][j]$。
(2)：假如我们取这个物品,那么 $dp[i][j]$ 是从什么情况转移呢？思考一下，首先可以得出， $dp[i][j]$ 肯定可以从上一个物品转移过来，那可以从什么体积转移呢？我们注意到，对于 $dp[i][j]$ ，它的当前取到的体积为 $j$，由于我们取了这个物品，所以上一个物品的体积为 $j-c[i]$。所以我们可以得出， $dp[i][j]$ 可以从 $dp[i-1][j-c[i]]$ 转移过来，由于我们取了这个物品，所以还要加上这个物品的价值 $w[i]$ 。
所以我们可以得出01背包的状态转移方程（很重要，尽量背下来！！）
$j>=c[i]$ 时，$dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])$
$j<c[i]$ 时，$dp[i][j]=dp[i-1][j]$。

上代码：

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

int dp[21][1010];
int w[21], c[21];
int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> c[i];
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= V; j++) {
            if (j >= c[i]) {
                dp[i][j] = max(dp[i - 1][j - c[i]] + w[i], dp[i - 1][j]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout << dp[N][V] << endl;
    return 0;
}

01背包滚动数组空间优化

我们分析一下空间复杂度：$O(NV)$，显然较大，我们要优化一下，用什么优化呢？
我们可以用滚动数组！
观察转移方程，易得 $dp[i][j]$ 只从 $dp[i-1][j]$ 和 $dp[i-1][j-c[i]]$转移，所以可以用一个$flag$代替 $i$，用 $1-flag$ 代替 $i-1$。

这样只需要定义 $dp[2][maxn]$ ,大大节省了空间。

上代码：

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

int dp[2][1010];
int w[21], c[21];

int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> c[i];
    }
    int flag = 1;
    for (int i = 1; i <= N; i++) {
        for(int j = 0;j <= V; j++) {
            if(j >= c[i]) {
                dp[flag][j] = max(dp[1 - flag][j - c[i]] + w[i], dp[1 - flag][j]);
	    } else {
                dp[flag][j] = dp[1 - flag][j];
	    }
	}
        flag = 1 - flag;
    }
    cout << dp[1 - flag][V] << endl;
    return 0;
}

01背包空间优化

这里给大家介绍真正的空间优化。

如果我们将 $dp$ 数组只用来表示体积，那么我们可以让内层循环的 $j$ 从 $V$ 到 $0$ 枚举，那么当前状态转移方程的 $dp[j]$ 和 $dp[j-c[i]]$ 由于我们没有更新，所以仍然是计算上一轮 $i-1$ 个物品的，就是二维状态下的 $dp[1-flag][j]$ 和 $dp[i-flag][j-c[i]]$。所以现在我们的转移方程是：
$dp[j]=max(dp[j],dp[j-c[i]]+w[i])$

上代码：

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

int dp[1010];
int w[21], c[21];

int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> c[i];
    }
    for (int i = 1; i <= N; i++) {
		for (int j = V; j >= c[i]; j--) {
            dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
		}
    }
    cout << dp[V] << endl;
    return 0;
}

课后习题

采药
开心的金明