锐客网

  1. 首页 > it技术 > >

背包九讲--混合背包和分组背包问题

混合背包顾名思义是讲0/1，多重和完全背包混合起来的背包问题，我们处理这种背包问题一般是进行条件判断处理然后在进行三个背包问题分析就可以了。
实战项目：https://www.acwing.com/problem/content/description/7/
https://www.luogu.com.cn/problem/P1833；
代码以及注意事项如下：
背包九讲--混合背包和分组背包问题
文章图片



1 //没有注意事项，前面的问题分析都有，不多重复 2 #include 3 using namespace std; 4 intdp[10100]; 5 int n,v; 6 int value,weight,s; 7 int main() 8 { 9ios::sync_with_stdio(false); 10cin>>n>>v; 11for (register int i = 1; i <= n; i++) { 12cin >>weight>>value>>s; 13if (s== 0) 14for (int j = weight; j <= v; j++) 15dp[j] = max(dp[j], dp[j - weight] + value); 16else if (s== -1) 17for (int j = v; j >=weight; j--) 18dp[j] = max(dp[j], dp[j -weight] +value); 19else { 20int num = min(s, v /weight); 21for (int k = 1; num > 0; k <<= 1) { 22if (k > num) 23k = num; 24num -= k; 25for (int j = v; j >= weight * k; j--) 26dp[j] = max(dp[j], dp[j - weight * k] +value* k); 27} 28} 29 } 30cout<
2.分组背包问题：
有 N组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是vij，价值是wij，其中 i是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值
这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选
那我们可以这样处理：
for (int i = 1; i <= n; i++) { cin >> s; for (int j = 1; j <= s; j++) cin >> c[j] >> w[j]; for (int j = v; j >= 0; j--) for (int k = 1; k <= s; k++) if (j >= c[k]) f[j] = max(f[j], f[j - c[k]] + w[k]); }

需要注意的是，对于三层for循环必须要保证j循坏在k循环的外面才能保证取物品是不冲突的，达到分组背包的目的；
项目实战：
https://www.acwing.com/problem/content/description/9/
https://www.luogu.com.cn/problem/P1757#sub
1 #include 2 using namespace std; 3 int n,v; 4 int f[1010]; 5 int s; 6 int c[1010]; 7 int w[1010]; 8 int main() 9 { 10ios::sync_with_stdio(false); 11cin>>n>>v; 12 for (int i = 1; i <= n; i++) { 13cin >> s; 14for (int j = 1; j <= s; j++) cin >> c[j] >> w[j]; 15for (int j = v; j >= 0; j--) 16for (int k = 1; k <= s; k++) 17if (j >= c[k]) 18f[j] = max(f[j], f[j - c[k]] + w[k]); 19 20 } 21 22cout<
洛谷：
1 #include 2 using namespace std; 3 int dp[1010]; 4 int weight[1010]; 5 int value[1010]; 6 int s[1010]; 7 int n,m; 8 int com; 9 int main() 10 { 11ios::sync_with_stdio(false); 12cin>>m>>n; 13for(register int i=1; i<=n; i++) 14{ 15cin>>weight[i]>>value[i]>>s[i]; 16com=max(com,s[i]); //确定组数 17} 18for(register int i=1; i<=com; i++)//对组进行循环 19{ 20for(register int j=m; j>=0; j--)//对重量进行循环 21{ 22for(register int k=1; k<=n; k++)//对物品进行循环 23{ 24if(s[k]!=i||j

背包九讲--混合背包和分组背包问题
文章图片

【背包九讲--混合背包和分组背包问题】

    推荐阅读


    上一篇：mysql|Mysql窗口函数-自用

    下一篇：使用Docker方式安装Jenkins