LeetCode刷题笔记——背包问题汇总
2022-04-03
符号说明
C: 背包容量(重量)N: 物品种类数weights: 每种物品的重量values: 每种物品的价值amounts: 每种物品的数量
为了避免下标访问引起的混淆，这里规定物品编号从1开始weights和values、amounts从下标1开始为有效数据dp[0][] 表示不放物品的情况
01背包
说明：每种物品只有1个
基本实现
时间复杂度，空间复杂度
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，取最大值改为累加，详见下面的其他情形
状态压缩
时间复杂度，空间复杂度
上面的基本实现中，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\sum(C/w_i))$，空间复杂度$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];
}
优化实现
时间复杂度，空间复杂度
上面的基本实现中，存在较多的不必要的状态转移
考虑第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];
}
优化实现+状态压缩
时间复杂度，空间复杂度
类似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 种物品拆分成费用为 $w_i 2^k$、价值为 $v_i 2^k$ 的若干件物品，其中 $k$ 取遍满足 $0 ≤ w_i 2^k ≤ C$ 的非负整数。、
这样一来就把每种物品拆成 $O(log⌊C/w_i⌋)$ 件物品，时间复杂度大大改进。
这种方法利用了二进制拆分思想，相当于把第 i 种物品按 1, 2, 4, 8, ..., 2^k 件进行打包
不管原最优策略最终选多少件第 i 种物品，
其件数写成二进制后，总可以对应表示成若干个 “2^k件物品” 的和。
多重背包
说明：每种物品有若干个
基本实现
时间复杂度$O(NC\sum(min(C/w_i, a_i)))$，空间复杂度$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];
}
基本实现+状态压缩
时间复杂度，空间复杂度
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;
}