关于分组背包问题(入门) 笔记
2024-08-14 17:08:15
发布于:广东
分组背包问题
目录
1——问题概览
2——处理"分组"
问题概览
难度:普及 题目:YBT1272 分组背包模版
本文以YBT1272 分组背包模版作为讲解
题目描述:
一个旅行者有一个最多能装公斤的背包,现在有件物品,它们的重量分别是
它们的价值分别为。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
处理"分组"
分组背包不同于01背包,它限定了小组,问题就变为了是选择这个小组中的某一件,还是都不选
按照01背包的原理我们可以很容易定义出表的状态,为第组且可用空间为下所能获得的最大价值
设若物品为组中的,则状态转移方程就是
当然,分组背包也是可以优化到一维
在遍历操作的时候开三层的循环,枚举小组,可用容量还有组内的每一个物品
注意枚举容量应在枚举组内物品外层,因为要保证一组中只有一个物品被拿,不然会出现01背包优化后采用顺推的情况,那样就是完全背包了
就像01背包的优化后是采用逆推保证它只拿一次,分组背包没采用逆推而是改变循环层序起到保证的效果
详解在注释里,实现代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll V,N,T;//背包容量 物品数量 最大组号
struct Thing{ll w,c,p;}a[35];//物品结构体
ll group[15][35];//小组数组 第一个位为小组编号 第二个为k组中物品的编号
ll DP[205];//容量为j下所能获得的最多价值
ll maxn(ll x,ll y){
return x>y? x:y;
}
int main(){
cin>>V>>N>>T;
for(int i=1;i<=N;i++){
cin>>a[i].w>>a[i].c>>a[i].p;
group[a[i].p][++group[a[i].p][0]]=i;//存储编号
//每组的第0位存储有多少个物品属于这一组,即group[p][0]
}
for(int i=1;i<=T;i++){//枚举每个组
for(int j=V;j>=0;j--){//枚举容量
for(int k=1;k<=group[i][0];k++){//枚举组内的每件物品
if(a[group[i][k]].w>j){//如果超过上限,跳过
continue;
}
DP[j]=maxn(DP[j],DP[j-a[group[i][k]].w]+a[group[i][k]].c);
}
}
}
cout<<DP[V];
return 0;
}
这里空空如也
有帮助,赞一个