目录
- 前言
- 01背包
- 完全背包
- 多重背包之 简单拆分
- 多重背包之 二进制拆分
- 混合背包
- 二维费用的背包问题
- 分组背包问题
- 有依赖关系的背包问题
前言
今天复（yu）习背包问题。。。 其实之前背包问题，我也写过，但是属实写的太拉跨了，今天写一波重制版。。。
背包算是一个经典的dp问题了。大概思路是这样：用一个体积为 V 的背包，选择一系列物品装进去。每个物品有他的价值 W
问：在不超过背包最大体积的情况下，能够获取的物品最大价值是多少？
01背包
原题链接：/problem/content/2/
题目描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
- 1
- 2
输入样例
4 5
1 2
2 4
3 4
4 5
- 1
- 2
- 3
- 4
- 5
输出样例：
8
- 1
解答
01背包非常经典，万物起源 。现有容量为 V 的背包，对第 x 个物品有两种选择，即
- 选它，问题转换为在前 x-1 个物品中，用容量 V-weight[x] 进行选择
- 不选它，问题转换为在前 x-1 个物品中，用容量 V 进行选择
我们结果取最大即可。。。这里使用记忆化搜索，边界条件是容量用完，或者物品用完：
#include <bits/stdc++.h>
using namespace std;
int n, v, dp[1009][1009];
vector<int> volumn, weight, amont;
int ms(int x, int V)
{
// 边界
if(x<0 || V<=0) return 0;
// 记忆化
if(dp[x][V]!=-1) return dp[x][V];
// 递推
int ans1=0, ans2=0;
ans1 = ms(x-1, V); // 不选
if(V-volumn[x]>=0) // 选
ans2 = ms(x-1, V-volumn[x]) + weight[x];
int ans = max(ans1, ans2); // 取最大
dp[x][V] = ans;
return ans;
}
int main()
{
memset(dp, -1, sizeof(dp));
cin>>n>>v;
for(int i=0; i<n; i++)
{
int vi, wi; cin>>vi>>wi;
volumn.push_back(vi);
weight.push_back(wi);
}
cout<<ms(n-1, v)<<endl;
return 0;
}
- 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
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
完全背包
原题链接：/problem/content/3/
题目描述
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
- 1
- 2
输入样例
4 5
1 2
2 4
3 4
4 5
- 1
- 2
- 3
- 4
- 5
输出样例：
10
- 1
解答
和 01 背包类似，只是我们可以选多次相同物品，我们只需要在 01 背包的基础上，修改转移方程即可：
如图，因为体积从小到大枚举（递归顺序保证我们总是优先解决体积小的背包），保证不会遗漏状态。
因为体积不断变大，能够进行的选择只会越来越多。
代码
#include <bits/stdc++.h>
using namespace std;
int n, v, dp[1009][1009];
vector<int> volumn, weight, amont;
int ms(int x, int V)
{
// 边界
if(x<0 || V<=0) return 0;
// 记忆化
if(dp[x][V]!=-1) return dp[x][V];
// 递推
int ans1=0, ans2=0;
ans1 = ms(x-1, V); // 不选
if(V-volumn[x]>=0) // 选
ans2 = ms(x, V-volumn[x]) + weight[x];
int ans = max(ans1, ans2);
dp[x][V] = ans;
return ans;
}
int main()
{
memset(dp, -1, sizeof(dp));
cin>>n>>v;
for(int i=0; i<n; i++)
{
int vi, wi; cin>>vi>>wi;
volumn.push_back(vi);
weight.push_back(wi);
}
cout<<ms(n-1, v)<<endl;
return 0;
}
- 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
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
多重背包之 简单拆分
原题链接：/problem/content/4/
题目描述
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<vi,wi,si≤100
- 1
- 2
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
- 1
- 2
- 3
- 4
- 5
输出样例：
10
- 1
解答
amont[i] 表示第 i 种物品的数量，对于每种物品，我们可以选 amont[i] 次
那么我们将每种物品拆成 amont[i] 个物品，然后用01背包进行求解即可：
代码：
#include <bits/stdc++.h>
using namespace std;
int n, v, dp[3009][3009];
vector<int> volumn, weight, amont;
int ms(int x, int V)
{
// 边界
if(x<0 || V<=0) return 0;
// 记忆化
if(dp[x][V]!=-1) return dp[x][V];
// 递推
int ans1=0, ans2=0;
ans1 = ms(x-1, V); // 不选
if(V-volumn[x]>=0) // 选
ans2 = ms(x-1, V-volumn[x]) + weight[x];
int ans = max(ans1, ans2);
dp[x][V] = ans;
return ans;
}
int main()
{
memset(dp, -1, sizeof(dp));
cin>>n>>v;
for(int i=0; i<n; i++)
{
int vi, wi, si; cin>>vi>>wi>>si;
volumn.push_back(vi);
weight.push_back(wi);
amont.push_back(si);
}
// 简单拆分 -- 每种物品拆成amont[i]个物品
vector<int> new_volumn, new_weight;
for(int i=0; i<n; i++)
{
for(int j=1; j<=amont[i]; j++)
{
new_volumn.push_back(volumn[i]);
new_weight.push_back(weight[i]);
}
}
volumn = new_volumn;
weight = new_weight;
n = volumn.size();
cout<<ms(n-1, v)<<endl;
return 0;
}
- 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
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
多重背包之 二进制拆分
原题链接：/problem/content/5/
题目描述
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
- 1
- 2
- 3
提示：
本题考查多重背包的二进制优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
- 1
- 2
- 3
- 4
- 5
输出样例：
10
- 1
解答
因为规模变大，我们无法通过简单拆解法拆解物品，我们需要做一个优化。
回想起二进制的思想，即假设我们拥有二进制的这么几个数，他们是3bit的：
001
010
100
- 1
- 2
- 3
那么我们可以用它们三个来表示 2^3 之内的所有数字：
十进制 二进制
0 = 000
1 = 001
2 = 010
3 = 011 = 010 + 001
4 = 100
5 = 101 = 100 + 001
6 = 110 = 100 + 010
7 = 111 = 100 + 010 + 001
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
同样，假设我们同一物品有 13 个，我们可以通过下面 4 个基础物品来表示 0-13 之内的任意数字：
1
2
4
6
- 1
- 2
- 3
- 4
注意最后为何不是 8 而是 6？如果是 8 的话，我们就会有1+2+4+8 = 15 件物品可选，超出题目限制的 13 件了。故所有拆分方式，最终的加和必须等于题目限制的数目。
如图：某种物品最多可选 13 件，我们拆成 1，2，4，6 合 1 的， 共 4 件物品
代码：注意原题的规模非常大，我们不好使用记忆搜索了。。。直接空间压缩的两行dp数组。其中
dp[0] -> dp[i-1]
dp[1] -> dp[i]
- 1
- 2
然后每次我们推完一行，都要将这一行向下滚动：
dp[0] = dp[1]; // 这一行变成上一行
- 1
#include <bits/stdc++.h>
using namespace std;
int n, v;
vector<int> volumn, weight, amont;
vector<vector<int> > dp;
int main()
{
// dp[0] -> dp[i-1]
// dp[1] -> dp[i]
dp.resize(2);
dp[0].resize(2009), dp[1].resize(2009);
cin>>n>>v;
for(int i=0; i<n; i++)
{
int vi, wi, si; cin>>vi>>wi>>si;
volumn.push_back(vi);
weight.push_back(wi);
amont.push_back(si);
}
// 二进制拆分为01背包
vector<int> new_volumn, new_weight;
for(int i=0; i<n; i++)
{
for(int j=1; j<=amont[i]; j*=2) // 1+2+4+...
{
amont[i] -= j;
new_volumn.push_back(volumn[i]*j);
new_weight.push_back(weight[i]*j);
}
if(amont[i]>0) // 剩余部分
{
new_volumn.push_back(volumn[i]*amont[i]);
new_weight.push_back(weight[i]*amont[i]);
}
}
volumn = new_volumn;
weight = new_weight;
n = volumn.size();
// 第一件物品
for(int i=0; i<=v; i++)
if(i>=volumn[0]) dp[0][i]=weight[0];
// 01背包
for(int i=1; i<n; i++)
{
for(int j=0; j<=v; j++)
{
int ans1=0, ans2=0;
ans1 = dp[0][j]; // dp[i-1][j]
if(j-volumn[i]>=0)
ans2 = dp[0][j-volumn[i]] + weight[i]; // dp[i-1][j-volumn[i]] + weight[i]
dp[1][j] = max(ans1, ans2); // dp[i][j] = max(ans1, ans2)
}
dp[0] = dp[1]; // 这一行变成上一行
}
cout<<dp[0][v]<<endl;
return 0;
}
- 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
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
混合背包
原题链接：/problem/content/7/
题目描述
有 N 种物品和一个容量是 V 的背包。
物品一共有三类：
- 第一类物品只能用1次（01背包）；
- 第二类物品可以用无限次（完全背包）；
- 第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
- si=−1 表示第 i 种物品只能用1次；
- si=0 表示第 i 种物品可以用无限次；
- si>0 表示第 i 种物品可以使用 si 次；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000
- 1
- 2
- 3
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
- 1
- 2
- 3
- 4
- 5
输出样例：
8
- 1
解答
都给你缝完了????
其实就是三种背包缝合一下。注意到三种背包的关系：
其中：
- 01背包就是最多选一次的多重背包
- 完全背包就是最多选
V / volumn[i]次的多重背包，其中 V 是总的背包体积，volumn[i] 是当前物品的体积
那么我们将 01 背包和完全背包转换为多重背包问题，之后直接利用二进制拆分的多重背包进行求解即可。对上文多重背包的代码稍加修改：
代码：
#include <bits/stdc++.h>
using namespace std;
int n, v;
vector<int> volumn, weight, amont;
vector<vector<int> > dp;
int main()
{
// dp[0] -> dp[i-1]
// dp[1] -> dp[i]
dp.resize(2);
dp[0].resize(2009), dp[1].resize(2009);
cin>>n>>v;
for(int i=0; i<n; i++)
{
int vi, wi, si; cin>>vi>>wi>>si;
if(si==-1) si=1; // 只能选一个
if(si==0) si=v/vi; // 最多选 v/wi 个
volumn.push_back(vi);
weight.push_back(wi);
amont.push_back(si);
}
// 二进制拆分为01背包
vector<int> new_volumn, new_weight;
for(int i=0; i<n; i++)
{
for(int j=1; j<=amont[i]; j*=2) // 1+2+4+...
{
amont[i] -= j;
new_volumn.push_back(volumn[i]*j);
new_weight.push_back(weight[i]*j);
}
if(amont[i]>0) // 剩余部分
{
new_volumn.push_back(volumn[i]*amont[i]);
new_weight.push_back(weight[i]*amont[i]);
}
}
volumn = new_volumn;
weight = new_weight;
n = volumn.size();
// 第一件物品
for(int i=0; i<=v; i++)
if(i>=volumn[0]) dp[0][i]=weight[0];
// 01背包
for(int i=1; i<n; i++)
{
for(int j=0; j<=v; j++)
{
int ans1=0, ans2=0;
ans1 = dp[0][j]; // dp[i-1][j]
if(j-volumn[i]>=0)
ans2 = dp[0][j-volumn[i]] + weight[i]; // dp[i-1][j-volumn[i]] + weight[i]
dp[1][j] = max(ans1, ans2); // dp[i][j] = max(ans1, ans2)
}
dp[0] = dp[1]; // 这一行变成上一行
}
cout<<dp[0][v]<<endl;
return 0;
}
- 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
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
二维费用的背包问题
原题链接：/problem/content/8/
题目描述
有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。输出最大价值。
输入格式
第一行两个整数，N，V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000
- 1
- 2
- 3
- 4
输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
- 1
- 2
- 3
- 4
- 5
输出样例：
8
- 1
解答
和 01 背包类似，多了一个维度限制罢了。。。转移方程类似的，我们直接记忆搜索即可：
#include <bits/stdc++.h>
using namespace std;
int n, v, m, dp[1009][109][109];
vector<int> volumn, mass, weight;
int ms(int x, int V, int M)
{
// 边界
if(x<0 || V<=0 || m<=0) return 0;
// 记忆化
if(dp[x][V][M]!=-1) return dp[x][V][M];
// 递推
int ans1=0, ans2=0;
ans1 = ms(x-1, V, M);
if(V-volumn[x]>=0 && M-mass[x]>=0)
ans2 = ms(x-1, V-volumn[x], M-mass[x]) + weight[x];
int ans = max(ans1, ans2);
dp[x][V][M] = ans;
return ans;
}
int main()
{
memset(dp, -1, sizeof(dp));
cin>>n>>v>>m;
for(int i=0; i<n; i++)
{
int vi, mi, wi; cin>>vi>>mi>>wi;
volumn.push_back(vi);
mass.push_back(mi);
weight.push_back(wi);
}
cout<<ms(n-1, v, m);
return 0;
}
- 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
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
分组背包问题
原题链接：/problem/content/9/
题目描述
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
- 每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
- 每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100
- 1
- 2
- 3
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
输出样例：
8
- 1
解答
和 01 背包类似，因为每组最多选一个，我们按组 dp 即可。对于组内的所有物品，我们分别遍历选取，最后取最大值。。。
设 dp[x][V] 表示在前 x 组，用体积为 V 的背包装，能够得到的最大价值。
- 如果该组不选，那么问题转换为：在前 x-1 组，用体积为 V 的背包装
- 如果该组选，那么问题转换为：在前 x-1 组，用体积为 V - volumn 的背包装。其中 volumn 为 x 组内物品的体积（需要遍历组内所有物品）
代码：
#include <bits/stdc++.h>
using namespace std;
int n, v, dp[109][109];
typedef struct goods
{
int volumn, weight;
goods(int v, int w){volumn=v;weight=w;}
}goods;
vector<vector<goods> > groups; // 按组存储每组物品
int ms(int x, int V)
{
// 边界
if(x<0 || V<=0) return 0;
// 记忆化
if(dp[x][V]!=-1) return dp[x][V];
// 递推
int ans1=0, ans2=0;
ans1 = ms(x-1, V); // 不选该组
// 遍历选组内所有物品
for(int i=0; i<groups[x].size(); i++)
{
int volumn = groups[x][i].volumn;
int weight = groups[x][i].weight;
if(V<volumn) continue;
ans2 = max(ans2, ms(x-1, V-volumn)+weight);
}
int ans = max(ans1, ans2); // 取最大
dp[x][V] = ans;
return ans;
}
int main()
{
memset(dp, -1, sizeof(dp));
cin>>n>>v;
groups.resize(n);
for(int i=0; i<n; i++)
{
int k; cin>>k;
for(int j=0; j<k; j++)
{
int vi, wi; cin>>vi>>wi;
groups[i].push_back(goods(vi, wi));
}
}
cout<<ms(n-1, v)<<endl;
return 0;
}
- 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
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
有依赖关系的背包问题
咕了。。
原题链接：/problem/content/10/
题目描述
输入格式
输出格式
数据范围
- 1
输入样例
- 1
输出样例：
- 1
解答