Vecotor : 分组背包
2025-05-03 14:04:12
发布于：上海
8阅读
0回复
0点赞
题目概述：
分组背包
时间限制：1000ms
内存限制：128MB
一个旅行者有一个最多能装 V 公斤的背包，现在有 n 件物品，它们的重量分别是 W1,W2,...,Wn，它们的价值分别为 C1,C2,...,Cn 这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
输入格式
第一行：三个整数，V(背包容量，1≤V≤200)，N(物品数量，1≤N≤30)和 T (最大组号，1≤T≤10)；
第 2..N+1 行：每行三个整数 Wi,Ci,Pi(1≤Wi≤V,1≤Ci≤1000,1≤Pi≤T)，表示每个物品的重量，价值，所属组号。
整体思路：
需要对每组物品做一个01背包
1、快速的遍历每一组的物品
需要将物品按组号分类 -- 二维 vector
vector<int> v[100];
v[0][0] = 1; # v[0].psuh_back(1);
2、需要遍历每个物品的两个属性
需要用结构体vector
struct node{
int w,c;
};
vector<node> v[100];
v[0].push({w,c});
3、AC代码：
#include<bits/stdc++.h>
using namespace std;
int v1,n,t;
struct node{
int w,v;
};
int dp[15][205];//第i组,容量为j的最大价值
vector<node> v[15];
int main(){
cin>>v1>>n>>t;
for(int i=0;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
v[c].push_back({a,b});
}
for(int i=1;i<=t;i++){
for(int j=0;j<=v1;j++){
dp[i][j] = dp[i-1][j];//提前计算不放入的情况
for(int k=0;k<v[i].size();k++){//k遍历某一组物品的数量 0 ~ v[i].size()-1
if(j >= v[i][k].w)
dp[i][j] = max(dp[i][j],dp[i-1][j-v[i][k].w]+v[i][k].v);
}
}
}
//答案
cout<<dp[t][v1];
return 0;
}
注意：for(int k=0;k<v[i].size();k++)不要写成for(int k=0;k<=v[i].size()-1;k++)不然会RE,这个点差点给我卡死了
适用于数据偏大的一维dp代码：
#include<bits/stdc++.h>
using namespace std;
int v1,n,t;
struct node{
int w,c;
};
int dp[10005];//容量为j的最大价值
vector<node> v[100005];
int main(){
cin>>v1>>n>>t;
for(int i=0;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
v[c].push_back({a,b});
}
for(int i=1;i<=t;i++)
for(int j=v1;j>=0;j--)
for(int k=0;k<v[i].size();k++)
if(j>=v[i][k].w)dp[j] = max( dp[j] , dp[j-v[i][k].w] + v[i][k].c);
cout<<dp[v1];
return 0;
}
这里空空如也
有帮助，赞一个