01背包问题

xiufanivan · 2023-03-13 11:19:39 · 个人记录

题目描述：

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

输入格式：

第一行输入n件商品，和背包容量b。

第二行开始，输入n行数据，第n行代表商品编号为n-2的商品信息，一行的第一个数据是商品重量w，第二个数据是商品价值v。

输出格式：

打印背包里最大的物品价值总和。

样例输入：

样例输出：

思路：

参考：代码随想录 - 01背包

确定dp数组（dp table）以及下标的含义：i：商品编号，j：背包容量，dp[i][j]：从编号 0 - i 的商品中任意取，再放进容量为 j 的背包中的最大价值。
确定递推公式：
- 不放商品 i ：dp[i][j] = dp[i - 1][j]，第 i 个商品若不放，则0 - i 中任取与 0 - i - 1一样。
- 放商品 i ：dp[i][j] = dp[i - 1][j - weight[i]] + value[i]，现确定放商品 i ，所以要加上value[i]，然后还要加上上一状态，上一状态要除去商品 i ，要在 0 - i - 1 中任取，背包容量也要减去商品 i 的重量，即dp[i - 1][j - weight[i]] + value[i]。

所以递推公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

dp数组如何初始化：
- 初始化由递推公式确定，因为递推公式中有 i - 1 ，所以第一行需要初始化。然后，递推公式中有 j - weight[i] ，j 必须 >= weight[i] 时，才能放进背包，即 j - weight[i] >= 0 ，所以 j < weight[0] 的列需要初始化。
- 如果背包容量 j < weight[0] 的话，无论是选取哪些物品，背包价值总和一定为0，所以 j < weight[0] 的列初始化为0 。
- 第一行，dp[0][j]，即：i 为 0 ，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。
确定遍历顺序：先遍历商品还是背包都可以。
举例推导dp数组

代码：

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

const int MAX = 100;

int n, b;  // n：商品种类数量，b：背包容量 
int weight[MAX] = {0}, value[MAX] = {0};  // weight：商品重量，value：商品价值 
vector<vector<int> > dp(MAX, vector<int>(MAX, 0));  //dp数组，表示最大价值 

void test_01bag() {
    // 初始化
    for (int j = weight[0]; j <= b; j++) {
        dp[0][j] = value[0];
    } 

    // 遍历
    for (int i = 1; i < n; i++) {  // 遍历商品 
        for (int j = weight[0]; j <= b; j++) {  // 遍历背包容量
            if (j < weight[i]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }
}

int main() {
    // 数据输入 
    cin >> n >> b;

    for (int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
    }
    // 填dp数组
    test_01bag();

    // 打印答案
    cout << dp[n - 1][b] << endl; 

    return 0;
}