经典背包问题2——混合背包问题、二维费用的背包问题、分组背包问题
- 1. 混合背包问题
- 2. 二维费用的背包问题
- 3. 分组背包问题
1. 混合背包问题 有 N 种物品和一个容量是 V的背包。
物品一共有三类：
- 第一类物品只能用1次（01背包）；
- 第二类物品可以用无限次（完全背包）；
- 第三类物品最多只能用 si次（多重背包）；
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i种物品的体积、价值和数量。
si=?1表示第 i种物品只能用1次；
si=0表示第 i种物品可以用无限次；
si>0表示第 i 种物品可以使用 si次；
输出格式
输出一个整数，表示最大价值。
数据范围
0
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例：
8
动态规划思路：
- 根据之前的经验，多重背包可以转化为01背包问题看待，而完全背包就按照完全背包看待，我们只需要把这两种方式区别开来，然后再针对性地进行选取就好了。
- 依旧是确定状态
dp[i]代表背包i容量的时候，我们所能选取的物品价值最大是多少。 - 然后就是归类，我们可以开个结构体数组，把不同种类的背包问题放进去，然后选取的时候根据选取的是哪类，再进行针对性的选取。
#include
#include
#include
using namespace std;
const int N = 1010;
//根据数据范围，适当大一些，避免段错误
int n,m;
//物品种类和背包容积
vector dp(N);
struct good{
int flag;
//flag==-1代表是01背包问题，flag==0代表完全背包问题
int v,w;
};
vector goods;
int main(){
cin>>n>>m;
for(int i = 1;
i<=n;
i++){
int v,w,s;
cin>>v>>w>>s;
if(s<0){//01背包
goods.push_back({-1,v,w});
}else if(s==0){//完全背包
goods.push_back({0,v,w});
}else{//多重背包，根据二进制思想转化为01背包
for(int k = 1;
k<=s;
k*=2){
s -= k;
goods.push_back({-1,k*v,k*w});
}
if(s>0){
goods.push_back({-1,s*v,s*w});
}
}
}
for(auto g:goods){
if(g.flag<0){//01背包方案
for(int j = m;
j>=g.v;
j--){
dp[j] = max(dp[j],dp[j-g.v]+g.w);
}
}else{//完全背包方案
for(int j = g.v;
j<=m;
j++){
dp[j] = max(dp[j],dp[j-g.v]+g.w);
}
}
}
cout< 2. 二维费用的背包问题 有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。输出最大价值。
输入格式
第一行两个整数，N，V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i件物品的体积、重量和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
输出样例：
【动态规划|经典背包问题2——混合背包问题、二维费用的背包问题、分组背包问题】8
动态规划思路：
- 这道题其实也不难，就是把之前的一维问题提升为了二维，以前我们是看前n件物品，当总容量为v的时候价值最大，用的框架是先遍历物品，在里面嵌套容量即可，现在我们只需要在容量里再嵌套一层不同质量就行了。
- 定义
dp[i][j]为背包容量为i，质量为j的时候，所能装得下的最大价值是多少。 - 转移方程为：
dp[j][k] = max(dp[j][k],dp[j-a][k-b]+c);，意思是要么不选第i个物品，要么选第i个物品，此时dp为dp[j-a][k-b]+c，a是第i个物品的容量，b是质量，c是价值。
#include
#include
using namespace std;
const int N = 1010;
int dp[N][N];
int n,v,m;
int main(){
cin>>n>>v>>m;
for(int i = 0;
i>a>>b>>c;
for(int j = v;
j>=a;
j--){
for(int k = m;
k>=b;
k--){
dp[j][k] = max(dp[j][k],dp[j-a][k-b]+c);
}
}
}
cout< 3. 分组背包问题 有 N 组物品和一个容量是 V的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是
vij，价值是 wij，其中 i 是组号，j是组内编号。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N组数据：
每组数据第一行有一个整数 Si，表示第 i个物品组的物品数量；
每组数据接下来有 Si行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例：
8
动态规划思路：
??有了之前几种题型的训练，这道题的思想就很简单了，因为每一组里只能选择一个，那么就是把每一组看成一个整体，然后再整体使用01背包。（注意：最后一层嵌套是尝试选择各组里面的物品）
代码：
#include
#include
using namespace std;
const int N = 110;
int dp[N],v[N],w[N];
int n,m;
int main(){
cin>>n>>m;
for(int i = 0;
i>s;
for(int j = 0;
j;
j++){
cin>>v[j]>>w[j];
}
for(int j = m;
j>=0;
j--){
for(int k = 0;
k;
k++){
if(j>=v[k]) dp[j] = max(dp[j],dp[j-v[k]]+w[k]);
}
}
}
cout< 推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络