Skip to main content

背包问题

01 背包​

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

动规五部曲:

  1. 确定 dp 数组以及下标的含义，dp[i][j] 表示从 [0, i] 物品中任意选择，放进容量为 j 的背包，能够获得的最大价值

  2. 确定递推公式:

    dp[i] [j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);，其中 j-weight[i] 表示要腾出来 weight[i] 大小的空间。

    使用滚动数组的话，递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

  3. dp 数组初始化

  4. 确定遍历顺序

  5. 举例推导 dp 数组

一维滚动数组解法:

void test_1_wei_bag_problem() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

    // 初始化
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}

int main() {
    test_1_wei_bag_problem();
}

完全背包问题​

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包问题和 01 背包问题唯一不同的地方是物品有无限个。

一维滚动数组解法:

// 先遍历物品，在遍历背包
void test_CompletePack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    test_CompletePack();
}