前言：
今日刷题发现蓝桥杯好多dp问题。
刚好刷到了一道01背包问题，简单地AC后，将全部的背包问题复习了一下
接下来让我浅浅地分享一下背包问题家族
概述：
背包问题一共有三大类:01背包、完全背包、多重背包。
01背包：
01背包问题是比较简单的，简单来说就是每种物品只能选一次，在有限的体积下选取价值最大的。之所以称之为01背包问题，是因为在只有二进制的计算机中0常常表示否，也就是拒绝，1恰巧相反。
01背包常见的模板如下
1
2
3
4
| for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
|
完全背包:
完全背包与01背包的不同在于完全背包的每种物品有无数件，只要空间足够可以无限取。
完全背包常见的模板如下
1
2
3
4
5
| for(int i=1;i<=n;i++){
for(int j=v[i];j<=v;j++){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
|
多重背包：
多重背包在01背包上加了特殊条件，每种物品都有特定的件数，所以可以将多重背包转化为01背包
多重背包常见的模板如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| for(int i=1;i<=n;i++){
int t=1;
while(s>=t){
xb++;
v[xb]=t*vi,w[xb]=wi*t;
t*=2;
s-=t;
}
while(s){
xb++;
v[xb]=s*vi,w[xb]=s*wi;
}
}
for(int i=1;i<=xb;i++){
for(int j=V;j>=v[i];j--){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
|
简单地介绍一下，接下来让我们实践一下。
实践
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的空间是 C i ，得到的价值是 W i 。求解在不超过容量的前提下，将哪些物品装入背包可使价值总和最大。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
using namespace std;
const int N=105;
int dp[N];
int n,V;
int w[N],v[N];
int main(){
cin>>n>>V;
for(int i=1;i<=n;i++){
cin>>v[i];
}
for(int i=1;i<=n;i++){
cin>>w[i];
}
for(int i=1;i<=n;i++){
for(int j=V;j>=v[i];j--) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout<<dp[V];
return 0;
}
|
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
using namespace std;
const int N=35;
int n,V;
int v[N],w[N],dp[N];
int main(){
cin>>V>>n;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++){
for(int j=v[i];j<=V;j++){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[V];
return 0;
}
|
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi ，价值是 wi 。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
using namespace std;
const int N=105;
int v[N],w[N],dp[N];
int vi,wi;
int n,V,xb,s;
int main(){
cin>>n>>V;
for(int i=1;i<=n;i++){
cin>>vi>>wi>>s;
int t=1;
while(s>=t){
xb++;
w[xb]=wi*t,v[xb]=vi*t;
s-=t;
t<<1;
}
if(s){
xb++;
w[xb]=wi*s,v[xb]=vi*s;
}
}
for(int i=1;i<=xb;i++){
for(int j=V;j>=v[i];j--){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[V];
return 0;
}
|
