Loading [MathJax]/jax/output/HTML-CSS/jax.js
LeetCode刷题笔记——背包问题汇总
2022-04-03

符号说明

C: 背包容量(重量)
N: 物品种类数
weights: 每种物品的重量
values: 每种物品的价值
amounts: 每种物品的数量

为了避免下标访问引起的混淆，这里规定物品编号从1开始
weights和values、amounts从下标1开始为有效数据
dp[0][] 表示不放物品的情况

01背包

说明：每种物品只有1个

基本实现

时间复杂度O(NC)，空间复杂度O(NC)

int knapsack01(const int C, const int N, vector<int>& weights, vector<int>& values) {
    vector<vector<int>> dp(N + 1, vector<int>(C + 1, 0)); //dp[i][j]为前i种物品(选择若干或全部)放入容量j的包能取得的最大价值，初始化为0
    for (int i = 1; i <= N; i++) { //枚举第i种物品，此时前i-1种物品已决定是否放入
        for (int j = 1; j <= C; j++) { //枚举容量j，正序逆序都可以
            dp[i][j] = dp[i - 1][j]; //不选第i种物品的情况，继承放入前i-1种物品的情况
            if (j >= weights[i]) { //当前容量够大，能放第i种物品才选
                dp[i][j] = max(dp[i][j], dp[i - 1][j - weights[i]] + values[i]);
            }
        }
    }
    return dp[N][C];
}

注意：对于计数类问题，dp[0][0]一般应该初始为1，取最大值改为累加，详见下面的其他情形

状态压缩

时间复杂度O(NC)，空间复杂度O(C)

上面的基本实现中，dp[i][]仅依赖于dp[i-1][]，即当前行仅依赖上一行，因此可以去除第一维（物品）
去除第一维后dp数组变为单行，相当于在原来的上一行直接修改，所以需要注意修改顺序，必须逆序枚举容量

int knapsack01(const int C, const int N, vector<int>& weights, vector<int>& values) {
    vector<int> dp(C + 1, 0); //在第i次循环开始时，dp[j]为前i-1种物品(选择若干或全部)放入容量j的包能取得的最大价值
    for (int i = 1; i <= N; i++) { //枚举第i种物品，此时0~i-1号物品已决定是否放入
        for (int j = C; j >= weights[i]; j--) { //枚举容量j，必须逆序
            //因为依赖上一行的数据在j较小的位置，逆序遍历不会覆盖需要的上一行数据
            //当前容量够大，能放第i种物品才选，最小容量只需遍历到weights[i]
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
            //max中的dp[j]是上一次外循环的结果，赋值后dp[j]原地更新为本次外循环的结果
            //dp[j - weights[i]]还是上一次外循环的结果，因为是逆序遍历j
        }
        //不选第i种物品的情况(j<weights[i])，继承放入前i-1种物品的情况，dp[j]不修改
    }
    return dp[C];
}

完全背包

说明：每种物品不限量

基本实现

时间复杂度O(NC∑(C/wi))，空间复杂度O(NC)

int knapsackComplete(const int C, const int N, vector<int>& weights, vector<int>& values) {
    vector<vector<int>> dp(N + 1, vector<int>(C + 1, 0)); //dp[i][j]为前i种物品(任选若干种若干个)放入容量j的包能取得的最大价值，初始化为0
    for (int i = 1; i <= N; i++) { //枚举第i种物品，此时前i-1种物品已决定放入多少个
        for (int j = 1; j <= C; j++) { //枚举容量j，正序逆序都可以
            for (int k = 0; k <= j / weights[i]; k++) { //枚举第i种物品放入的个数，包括0个(不选)，最多不超过当前容量j
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * weights[i]] + k * values[i]);
            }
        }
    }
    return dp[N][C];
}

优化实现

时间复杂度O(NC)，空间复杂度O(NC)

上面的基本实现中，存在较多的不必要的状态转移

考虑第i个物品重量为w，
计算容量j的情况时，dp[i][j] 从 dp[i - 1][j], dp[i - 1][j - w], dp[i - 1][j - 2w], .. ,dp[i - 1][j - kw], .. 转移
而事实上，计算容量j - w的情况时，dp[i][j - w] 已从 dp[i - 1][j - w], dp[i - 1][j - 2w], dp[i - 1][j - 3w], .. ,dp[i - 1][j - kw], .. 转移
所以 dp[i][j] 可以只从 dp[i - 1][j] 和 dp[i][j - w] 转移，去除对k的循环
注意到，dp[i][j] 对 dp[i][j - w] 的依赖，因此只能正序枚举容量

int knapsackComplete(const int C, const int N, vector<int>& weights, vector<int>& values) {
    vector<vector<int>> dp(N + 1, vector<int>(C + 1, 0)); //dp[i][j]为前i种物品(任选若干种若干个)放入容量j的包能取得的最大价值，初始化为0
    for (int i = 1; i <= N; i++) { //枚举第i种物品，此时前i-1种物品已决定放入多少个
        for (int j = 1; j <= C; j++) { //枚举容量j，必须正序
            dp[i][j] = max(dp[i - 1][j], dp[i][j - weights[i]] + values[i]);
        }
    }
    return dp[N][C];
}

优化实现+状态压缩

时间复杂度O(NC)，空间复杂度O(C)

类似01背包的状态压缩

int knapsackComplete(const int C, const int N, vector<int>& weights, vector<int>& values) {
    vector<int> dp(C + 1, 0); //在第i次循环开始时，dp[j]为前i种物品(任选若干种若干个)放入容量j的包能取得的最大价值
    for (int i = 1; i <= N; i++) { //枚举第i种物品，此时前i-1种物品已决定放入多少个
        for (int j = weights[i]; j <= C; j++) { //枚举容量j，必须正序
            //当前容量够大，能放第i种物品至少一个才选，最小容量只需从weights[i]开始
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
            //dp[j - weights[i]]是本次外循环的结果，因为是正序遍历j
            //上面的分析也提到dp[i][j] 对 dp[i][j - weights[i]]的依赖，i 同为本次外循环
            //max中的dp[j]是上一次外循环的结果，赋值后dp[j]原地更新为本次外循环的结果
        }
        //第i种物品放0个的情况(j<weights[i])，继承放入前i-1种物品的情况，dp[j]不修改
    }
    return dp[C];
}

转化为 01 背包问题

最简单的想法是：
考虑到第 i 种物品最多选 ⌊C/w_i⌋ 件，
可以把第 i 种物品拆分为 ⌊C/w_i⌋ 件费用及价值均一样的单件物品
因此直接套用01背包的方法，但时间复杂度并没有改进

更高效的转化方法是：
把第 i 种物品拆分成费用为 wi2k、价值为 vi2k 的若干件物品，其中 k 取遍满足 0≤wi2k≤C 的非负整数。、
这样一来就把每种物品拆成 O(log⌊C/wi⌋) 件物品，时间复杂度大大改进。
这种方法利用了二进制拆分思想，相当于把第 i 种物品按 1, 2, 4, 8, ..., 2^k 件进行打包
不管原最优策略最终选多少件第 i 种物品，
其件数写成二进制后，总可以对应表示成若干个 “2^k件物品” 的和。

多重背包

说明：每种物品有若干个

基本实现

时间复杂度O(NC∑(min(C/wi,ai)))，空间复杂度O(NC)

类似完全背包的基本实现，枚举物品数量需要考虑物品本身数量上限

int knapsackComplete(const int C, const int N, vector<int>& weights, vector<int>& values, vector<int>& amounts) {
    vector<vector<int>> dp(N + 1, vector<int>(C + 1, 0)); //dp[i][j]为前i种物品(任选若干种若干个)放入容量j的包能取得的最大价值，初始化为0
    for (int i = 1; i <= N; i++) { //枚举第i种物品，此时前i-1种物品已决定放入多少个
        for (int j = 1; j <= C; j++) { //枚举容量j，正序逆序都可以
            for (int k = 0; k <= min(j / weights[i], amounts[i]); k++) { //枚举第i种物品放入的个数，包括0个(不选)，最多不超过当前容量j和第i种物品的数量
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * weights[i]] + k * values[i]);
            }
        }
    }
    return dp[N][C];
}

基本实现+状态压缩

时间复杂度O(NC∑(min(C/wi,ai)))，空间复杂度O(C)

int knapsackComplete(const int C, const int N, vector<int>& weights, vector<int>& values, vector<int>& amounts) {
    vector<int> dp(C + 1, 0);
    for (int i = 1; i <= N; i++) { //枚举第i种物品，此时前i-1种物品已决定放入多少个
        for (int j = C; j >= weights[i]; j++) { //枚举容量j，必须逆序
            for (int k = 0; k <= min(j / weights[i], amounts[i]); k++) { //枚举第i种物品放入的个数，包括0个(不选)，最多不超过当前容量j和第i种物品的数量
                dp[j] = max(dp[j], dp[j - k * weights[i]] + k * values[i]);
            }
        }
    }
    return dp[C];
}

其他

二维背包

说明：背包有两种容量，每种物品有两种重量

以01背包为例

此时应该为dp数组增加1维，增加1层循环

int knapsack01_2(const int C1, const int C2, const int N, vector<int>& weights1, vector<int>& weights2, vector<int>& values) {
    vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(C1 + 1, vector<int>(C2 + 1)));
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= C1; j++) {
            for (int k = 0; k <= C2; k++) {
                dp[i][j][k] = dp[i - 1][j][k];
                if (j >= weights1[i] && k >= weights2[i]) {
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - weights1[i]][k - weights2[i]] + values[i]);
                }
            }
        }
    }
    return dp[N][C1][C2];
}

求能否恰好装满

以01背包为例

此时物品的价值无意义，dp数组的元素改为bool值

应该初始化dp数组为false，初始化dp[0][0]为true

转移过程改为或（||）

int knapsack01(const int C, const int N, vector<int>& weights) {
    vector<vector<bool>> dp(N + 1, vector<bool>(C + 1, false)); //
    dp[0][0] = true; //
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= C; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= weights[i]) {
                dp[i][j] ||= dp[i - 1][j - weights[i]];
            }
        }
    }
    return dp[N][C];
}

求恰好装满的最大价值

以01背包为例

应该初始化dp数组为-INF，初始化dp[0][0]为0，表示0容量0物品可以恰好装满，价值为0

转移过程中，取较大值时，-INF总是会被舍弃

最后结果dp[N][C]若为-INF，表示容量为C的包无法恰好装满(可以同时解决上一个问题)，否则表示可以装满的最大价值

int knapsack01(const int C, const int N, vector<int>& weights, vector<int>& values) {
    vector<vector<int>> dp(N + 1, vector<int>(C + 1, INT_MIN)); //初始化为负无穷
    dp[0][0] = 0; //
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= C; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= weights[i]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - weights[i]] + values[i]);
            }
        }
    }
    return dp[N][C] == INT_MIN ? -1 : dp[N][C];
}

求恰好装满的最少物品数量

以01背包为例

此时物品的价值均为1，表示一件物品

应该初始化dp数组为INF，初始化dp[0][0]为0，表示0容量0物品可以恰好装满且价值为0

转移过程改用min，取较小值时，INF总是会被舍弃

最后结果dp[N][C]若为INF，表示容量为C的包无法恰好装满，否则表示可以装满的最少物品数量

int knapsack01(const int C, const int N, vector<int>& weights) {
    vector<vector<int>> dp(N + 1, vector<int>(C + 1, INT_MAX)); //初始化为正无穷
    dp[0][0] = 0; //
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= C; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= weights[i]) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j - weights[i]] + 1);
            }
        }
    }
    return dp[N][C] == INT_MAX ? -1 : dp[N][C];
}

求恰好装满的方案总数

以01背包为例

此时物品的价值无意义，dp数组表示方案数

应该初始化dp数组为0，初始化dp[0][0]为1，表示1种方案：0容量0物品可以恰好装满

转移过程改用累加（+）

int knapsack01(const int C, const int N, vector<int>& weights) {
    vector<vector<int>> dp(N + 1, vector<int>(C + 1, 0)); //初始化为0
    dp[0][0] = 1; //
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= C; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= weights[i]) {
                dp[i][j] += dp[i - 1][j - weights[i]];
            }
        }
    }
    return dp[N][C];
}

求恰好装满或最大价值的方案

以01背包为例

一般可以新增一个数组，记录转移过程中某个容量装入的最后一个物品

vector<int> knapsack01(const int C, const int N, vector<int>& weights, vector<int>& values) {
    vector<vector<int>> dp(N + 1, vector<int>(C + 1, 0)); //若需要恰好装满，则初始化为负无穷
    vector<vector<int>> path(N + 1, vector<int>(C + 1, -1));
    dp[0][0] = 0; //
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= C; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= weights[i]) {
                int temp = dp[i - 1][j - weights[i]] + values[i];
                if (temp > dp[i][j]) {
                    dp[i][j] = temp;
                    path[i][j] = i;
                }
            }
        }
    }
    vector<int> items;
    for (int j = C, i = N; i >= 0; i--) {
        if (path[i][j] == i) {
            items.push_back(i);
            j -= weights[i];
        }
    }
    return items;
}

也可以直接由dp数组推出

vector<int> knapsack01(const int C, const int N, vector<int>& weights, vector<int>& values) {
    vector<vector<int>> dp(N + 1, vector<int>(C + 1, INT_MIN)); //初始化为负无穷
    dp[0][0] = 0; //
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= C; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= weights[i]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - weights[i]] + values[i]);
            }
        }
    }
    vector<int> items;
    for (int i = N, j = C; i >= 1; i--) {
        int w = weights[i], v = values[i];
        if (j >= w && dp[i][j] == dp[i - 1][j - w] + v) { //若是完全或多重背包，此处应该尝试多次减去
            j -= w;
            items.push_back(i);
        }
    }
    return items;
}

测试程序

#include <bits/stdc++.h>
using namespace std;
int main()
{
    const int C = 20;
    const int N = 9;
    vector<int> weights = {0,1,3,5,6,7,8,10,12,15};
    vector<int> values = {0,1,2,3,4,5,6,7,8,9};
    cout << knapsack01(C, N, weights, values) << endl;
    return 0;
}

相关题目

[416] 分割等和子集

[474] 一和零

[377] 组合总和 Ⅳ

[139] 单词拆分

[494] 目标和

[322] 零钱兑换

[518] 零钱兑换 II

[1049] 最后一块石头的重量 II

参考

动态规划之背包问题系列

收藏文章
表情删除后不可恢复，是否删除
取消
确定
图片正在上传，请稍后...
取消上传
评论内容为空！
还没有评论，快来抢沙发吧！
该评论已关闭!
blog正在使用畅言云评
去社区看看吧
去热评看看吧

热评话题

关闭
按钮 内容不能为空！
立刻说两句吧！ 查看0条评论
搜索
背景设置