六、分组背包

题记

一个旅行者有一个最多能装V公斤的背包和有N件物品，它们的重量分别是W[1]，W[2]，…,W[n]，它们的价值分别为C[1],C[2],…,C[n]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

算法

这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有$$f[k][v]=maxf[k-1][v],f[k-1][v-w[i]]+c[i]（物品i属于第k组）$$
使用一维数组的伪代码如下：

for 所有的组 kfor v=V..0for 所有的 i 属于组 kf[v]=max(f[v],f[v-w[i]]+c[i])

题目

1272：【例9.16】分组背包
【题目描述】
一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，…,Wn，它们的价值分别为C1,C2,…,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

【输入】
第一行：三个整数，V(背包容量，V≤200)，N(物品数量，N≤30)和T(最大组号，T≤10)；

第2…N+1行：每行三个整数Wi,Ci,P，表示每个物品的重量，价值，所属组号。

【输出】
仅一行，一个数，表示最大总价值。

【输入样例】

10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3

【输出样例】

20

代码

#include<bits/stdc++.h>
using namespace std;
int n,v,t;
int w[310],c[310],a[310][310],f[310];
//a[p][0]数组记录每组有多少物品 
int main() {cin>>v>>n>>t;for(int i=1; i<=n; i++) {int p;cin>>w[i]>>c[i]>>p;a[p][++a[p][0]]=i; }for(int p=1; p<=t; p++)for(int j=v; j>=0; j--)for(int i=1; i<=a[p][0]; i++)//循环每一组数据中的物品 if(j>=w[a[p][i]])//保证数组不会越界 f[j]=max(f[j],f[j-w[a[p][i]]]+c[a[p][i]]);//计算最大价值 cout<<f[v];//输出在v公斤时的最大价值 return 0;
}