背包DP：从采药到疯狂的采药

一、什么是背包DP？

有这样一类问题：你有一个容量有限的背包，还有一堆物品，每个物品有自己的重量和价值。你要选择一些物品放进背包，每装一件物品，你就会消耗对应容量，并获得对应价值。
问题是在不超过背包容量的前提下，让总价值最大。

这个问题似乎是个贪心，但仔细想，按上述说法，则价值高的物品优先，重量小的物品优先，那这两个属性谁更优先呢？无法抉择。 如果考虑单位价值高的优先：
假设有背包容量M = 10， 3件物品，重量价值分别为
5, 5
5, 5
6, 7
此时看单位价值，前两件物品单位价值为1，第三件物品单位价值为7/6大于1，但要是装第三件物品，则装不下前两件了，总共获得7，而前两件能同时装下，可以获得10，不应选第三件。
问题出在哪里？我们会发现，一件物品装不装，不但由自身属性决定，还要看其他物品的配合。当我装了上面第三件物品，会消耗容量6，剩下容量4，其他物品无法填充容量4，或者说无法和物品3配合。
这就是动态规划问题，一件物品装不装，要考虑其他物品动态决定。
具体说，假设总容量为M，对物品i，有重量w和价值c，如果我们要装i，则需要知道M-w这些剩余容量到底能装多少价值，M-w的值不固定，需要考虑所有可能性。
即背包DP的核心：递推所有可能的容量下，能装下的最大价值。

二、先看01背包

分析过程

image.png

二维01背包代码

#include <bits/stdc++.h>
using namespace std;

const int MAXT = 1005; 
const int MAXM = 105; 

int w[MAXM], v[MAXM];  // 每件物品重量 / 价值
int dp[MAXM][MAXT];    // dp[i][j]表示前i件物品，j容量下能过得的最大价值

int main() {
    int T, M;
    cin >> T >> M;
    for (int i = 1; i <= M; i++) {
        cin >> w[i] >> v[i];
    }
    // 遍历每一件物品
    for (int i = 1; i <= M; i++) {
        // 遍历每一个可能的容量
        for (int j = 1; j <= T; j++) {
            if (j >= w[i]) { // 当前容量大于等于此物品重量，可以装
                /*
                不装：继承dp[i-1][j]
                装：获得v[i]，消耗w[i]，其余空间能获得的价值：dp[i-1][j - w[i]] + v[i]
                */
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]); // 取最大
            } else {
                // 容量不够，只能不采，继承i-1件物品在此容量下的价值
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    cout << dp[M][T] << endl; // 输出最大容量下，M件物品能获得的最大价值。
    return 0;
}

这个代码可以直接通过洛谷采药的所有测试点。

三、01背包的一维空间优化：

上面的二维数组其实有点浪费空间。因为我们在计算dp[i][j]的时候，只用到了dp[i-1][...]这一行的数据，前面的行都没用了。所以我们可以去掉多行维度，即物品维度，只保留一行，递推每个容量。思路还是不变，只不过算出来所有行，都覆盖到这一个一维数组里。

第一步：定义一维状态

我们把二维数组dp[i][j]改成一维数组dp[j]，它的含义变成：

用不超过j的容量，能得到的最大价值。

第二步：思考怎么更新一维数组

原来的二维转移方程是：
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

现在我们要把它改成一维的。我们可以这样想：我们先让dp[j]保存的是dp[i-1][j]的值（也就是上一行的值）。然后我们计算新的dp[j]，也就是dp[i][j]。

这时候有个非常关键的问题：我们应该按什么顺序遍历j？

错误的顺序：正序遍历

如果我们从j=1到j=T正序遍历，会发生什么？
比如我们只有一个物品，w=1，v=2。

  • j=1时：dp[1] = max(dp[1], dp[0] + 2) = 2
  • j=2时：dp[2] = max(dp[2], dp[1] + 2) = 4
  • j=3时：dp[3] = max(dp[3], dp[2] + 2) = 6

你会发现，这个物品被我们选了好几次！这是因为当我们计算j=2的时候，dp[1]已经是更新过的值了（也就是选了一次这个物品之后的值），而不是原来的dp[i-1][2]。

这就变成了完全背包，而不是01背包了。
image-1.png

正确的顺序：倒序遍历

所以我们必须从j=T到j=1倒序遍历。这样，当我们计算dp[j]的时候，dp[j - w[i]]还是上一行的值，也就是还没被更新过的值。

这样就保证了每个物品只会被选一次。

一维01背包代码

#include <bits/stdc++.h>
using namespace std;

const int MAXT = 1005;

int w[105], v[105];
int dp[MAXT]; // 一维dp数组

int main() {
    int T, M;
    cin >> T >> M;
    for (int i = 1; i <= M; i++) {
        cin >> w[i] >> v[i];
    }

    for (int i = 1; i <= M; i++) {
        // 关键：倒序遍历容量
        for (int j = T; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << dp[T] << endl;
    return 0;
}

四、完全背包：

每件物品都有无限个。

第一步：对比01背包和完全背包的区别

01背包和完全背包的唯一区别就是物品能不能重复选。

  • 01背包：每个物品只能选一次 → 倒序遍历容量
  • 完全背包：每个物品可以选无限次 → 正序遍历容量

完全背包的代码和01背包几乎一模一样，只是把倒序遍历改成正序遍历就行了。

第二步：为什么正序遍历就是完全背包？

我们还是用刚才那个例子：物品w=1，v=2，T=3。
正序遍历：

  • j=1：dp[1] = max(dp[1], dp[0] + 2) = 2（选了1次）
  • j=2：dp[2] = max(dp[2], dp[1] + 2) = 4（选了2次）
  • j=3：dp[3] = max(dp[3], dp[2] + 2) = 6（选了3次）

正序遍历的时候，我们可以重复利用已经更新过的dp[j - w[i]]，也就是可以多次选同一个物品。这正好符合完全背包的要求。

第三步：写出完全背包代码

#include <bits/stdc++.h>
using namespace std;

const int MAXT = 10000005; 

int w[10005], v[10005];
long long dp[MAXT];

int main() {

    int T, M;
    cin >> T >> M;
    for (int i = 1; i <= M; i++) {
        cin >> w[i] >> v[i];
    }

    for (int i = 1; i <= M; i++) {
        // 关键：正序遍历容量
        for (int j = w[i]; j <= T; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << dp[T] << endl;
    return 0;
}

标签: none

评论已关闭