背包九讲
一、01背包问题
题目概览
有
N
N
N件物品和一个容量是
V
V
V的背包。每件物品只能使用一次。
第
i
i
i件物品的体积是
v
i
v_i
vi，价值是
w
i
w_i
wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数
N
，
V
N，V
N，V用空格隔开，分别表示物品数量和背包容积。
接下来有
N
N
N行，每行两个整数
v
i
,
w
i
v_i,w_i
vi,wi用空格隔开，分别表示第
i
i
i件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0
<
N
,
V
≤
1000
0<N,V≤1000
0<N,V≤1000
0
<
v
i
,
w
i
≤
1000
0<v_i,w_i≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
(一)先使用DP去做
思路：
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示只看前i个物品，总体积是j的情况下，总价值最大是多少
r e s u l t = m a x ( f [ n ] [ 0 − v ] ) result = max(f[n][0-v]) result=max(f[n][0−v])
状态转移公式:
- 不选第
i个物品， f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j] = f[i - 1][j] f[i][j]=f[i−1][j]; - 选第
i个物品， f [ i ] [ j ] = f [ i − 1 ] [ j − v [ i ] ] f[i][j] = f[i - 1][j - v[i]] f[i][j]=f[i−1][j−v[i]]
f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v [ i ] ] ) f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]]) f[i][j]=max(f[i−1][j],f[i−1][j−v[i]])
初始化工作： f [ 0 ] [ 0 ] = 0 f[0][0] = 0 f[0][0]=0
代码实现：
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m;
int f[N][N];
int v[N],w[N];
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];
for(int i = 1;i <= n;i++)
for(int j = 0;j <= m;j++){
f[i][j] = f[i - 1][j];
if(j >= v[i])
f[i][j] = max(f[i][j],f[i - 1][j - v[i]] + w[i]);
}
int res = 0;
for(int i = 0;i <= m;i++) res = max(res,f[n][i]);
cout << res << endl;
return 0;
}
(二)进行优化
思路：
目标一：省掉一维空间
一共就二维，所以，我们不妨每一维都试一试。
-
省去j那一维
显而易见，所有的操作都是基于这一维的，如果没有这一维，无法进行转移。
换一种说法，省去j这一维， f [ i ] f[i] f[i]数组的含义变成了前i个物品，总价值是多少，好像不太行吧。。。 -
省去i那一维
仔细观察，不难发现，所有的状态均是由
i - 1那一维转移过来的，所以，可以尝试使用滚动数组
即 f [ j ] f[j] f[j]中原先存的是 f [ i − 1 ] [ j ] f[i - 1][j] f[i−1][j]的数据，更新后变为 f [ i ] [ j ] f[i][j] f[i][j]的数据
我们先尝试，强行去掉一维
主体代码：for(int i = 1;i <= n;i++) for(int j = 0;j <= m;j++){ if(j >= v[i]) f[j] = max(f[j],f[j - v[i]] + w[i]); }那么，就有问题了,由于
j是从小到大循环， f [ j − v [ i ] ] f[j - v[i]] f[j−v[i]],它好像已经被更新过了，它对应的是原先的 f [ i ] [ j − v [ i ] ] f[i][j - v[i]] f[i][j−v[i]]，与我们想象的不符。所以，我们让 f [ j ] f[j] f[j]先更新，再让 f [ j − v [ i ] ] f[j - v[i]] f[j−v[i]]先更新即可。实现也非常简单，只需要把
j倒着循环即可。目标二：少一个循环
找答案的循环不需要啦！
原因:
初始化的时候，把所有的 f [ i ] f[i] f[i]都初始化成了0f [ m ] f[m] f[m]就是体积为 m m m的方案。
代码实现:
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m;
int f[N];
int v[N],w[N];
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];
for(int i = 1;i <= n;i++)
for(int j = m;j >= 1;j--){
if(j >= v[i])
f[j] = max(f[j],f[j - v[i]] + w[i]);
}
cout << f[m] << endl;
return 0;
}
二、完全背包问题
题目概览：
有
N
N
N种物品和一个容量是
V
V
V的背包，每种物品都有无限件可用。
第
i
i
i种物品的体积是
v
i
v_i
vi，价值是
w
i
w_i
wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数， N N N， V V V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N N N行，每行两个整数 v i v_i vi, w i w_i wi，用空格隔开，分别表示第 i i i种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0
<
N
,
V
≤
1000
0<N,V≤1000
0<N,V≤1000
0
<
v
i
,
w
i
≤
1000
0<v_i,w_i≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10
思路与解
对比 01 01 01背包，区别在于，每个物品有无限件可以选。
思路：
f
[
i
]
f[i]
f[i]表示总体积是i的情况下，最大价值是多少
r
e
s
u
l
t
=
m
a
x
(
f
[
0
…
m
]
)
result = max(f[0…m])
result=max(f[0…m])
刚开始的想法肯定很朴实，会这样写:
for(int i = 0;i < n;i++)
for(int j = m;j >= v[i];j--)//到这里都和01背包一样
for(int k = 0;k * v[i] <= j;k++)//依次尝试能放多少
f[j] = max(f[j],f[j - k * [i]] * w[i]);
但是时间复杂度太大了。。
优化：
for(int i = 0;i < n;i++)
for(int j = v[i];j <= m;j++)
f[j] = max(f[j],f[j - v[i]] + w[i]);
因为是从小到大枚举，所以
f
[
j
−
v
[
i
]
]
f[j - v[i]]
f[j−v[i]]已经算过了
考虑前
i
i
i个物品，包括第
i
i
i个物品，可能里面已经有一些第
i
i
i个物品了
证明:
数学归纳法
-
假设考虑前 i − 1 i-1 i−1个物品之后，所有的 f [ j ] f[j] f[j]都是正确的
-
来证明：考虑完第 i i i个物品后，所有的 f [ j ] f[j] f[j]也都是正确的
对于某个 j j j而言，如果最优解中包含 k k k个 v [ i ] v[i] v[i];
从小到大枚举的时候，一定会枚举到 f [ j − f ∗ v [ i ] ] f[j - f * v[i]] f[j−f∗v[i]]，那么这个状态就会用 f [ j − k ∗ v [ i ] − v [ i ] ] + w [ i ] f[j - k * v[i] - v[i]] + w[i] f[j−k∗v[i]−v[i]]+w[i]来更新它。
枚举到 f [ j − ( k − 1 ) ∗ v [ i ] − v [ i ] ] + w [ i ] f[j - (k - 1) * v[i] - v[i]] + w[i] f[j−(k−1)∗v[i]−v[i]]+w[i]包含1个 v [ i ] v[i] v[i]
…
所以 f [ j ] f[j] f[j]就一定枚举到有 k k k个 v [ i ] v[i] v[i]的情况
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m;
int f[N];
int main(){
cin >> n >> m;
for(int i = 0;i < n;i++){
int v,w;
cin >> v >> w;
for(int j = v;j <= m;j++)
f[j] = max(f[j],f[j - v] + w);
}
cout << f[m];//与上一题的原因一样，不需要比较
return 0;
}
三、多重背包问题
题目概览：
有
N
N
N种物品和一个容量是
V
V
V的背包。
第
i
i
i种物品最多有
s
i
s_i
si件，每件体积是
v
i
vi
vi，价值是
w
i
wi
wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，
N
N
N，
V
V
V,用空格隔开，分别表示物品种数和背包容积.
接下来有
N
N
N行，每行三个整数
v
i
v_i
vi,
w
i
w_i
wi,
s
i
s_i
si,分别表示第 i� 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0
<
N
,
V
≤
100
0<N,V≤100
0<N,V≤100
0
<
v
i
,
w
i
,
s
i
≤
100
0<v_i,w_i,s_i≤100
0<vi,wi,si≤100（注意，下面会改）
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
(一)最暴力的方法：
思路：
f [ i ] f[i] f[i]总体积是 i i i的情况下，最大价值是多少
for(int i = 0;i < n;i++)
for(int j = m;j >= v[i];j--)
f[j] = max(f[j],f[j - v[i]] + w[i],f[j - 2 * v[i]],...)
将f的所有值初始化为 0 0 0，结果为 f [ m ] f[m] f[m]
代码与解
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int n,m;
int f[N];
int main(){
cin >> n >> m;
for(int i = 0;i < n;i++){
int v,w,s;
cin >> v >> w >> s;
for(int j = m;j >= 0;j--)
for(int k = 1;k <= s && k * v <= j;k++)
f[j] = max(f[j],f[j - k * v] + k * w);
}
cout << f[m] << endl;
return 0;
}
(二)二进制优化
题目不变
数据范围
0
<
N
≤
1000
0<N≤1000
0<N≤1000
0
<
V
≤
2000
0 < V \le 2000
0<V≤2000
0
<
v
i
,
w
i
,
s
i
≤
2000
0<v_i,w_i,s_i\le2000
0<vi,wi,si≤2000
思路：
- 把一个多重背包问题变成一个01背包问题
我们可以把物品重复 s s s份，放到物品堆里去，每个物品就独立了，成功转化为一个01背包
例如，我们要把7拆成不同的方案
笨方法：1 1 1 1 1 1
每个1都有选和不选聪明一下，我们只需要1，2，4，就可以表示出来1~7的所有数了
-
那么，回归到题目，只需要 l o g ( s ) log(s) log(s)上取整个数即可
时间复杂度来到了可观的 1000 × 11 × 2000 = 2 × 1 0 7 1000\times11\times2000 = 2 \times 10 ^ 7 1000×11×2000=2×107
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
int n,m;
int f[N];
struct Good{
int v,w;
};
int main(){
vector<Good> goods;
cin >> n >> m;
for(int i = 0;i < n;i++){
int v,w,s;
cin >> v >> w >> s;
for(int k = 1;k <= s;k *= 2){
s -= k;
goods.push_back({v * k,w * k});
}
if(s > 0) goods.push_back({v * s,w * s});
}
for(auto good:goods)
for(int j = m;j >= good.v;j--)
f[j] = max(f[j],f[j - good.v] + good.w);
cout << f[m] << endl;
return 0;
}
多重背包还有单调队列优化，还有以下板块持续更新！