本文共 1369 字，大约阅读时间需要 4 分钟。

分组背包

Time Limit:10000MS Memory Limit:65536K
Total Submit:133 Accepted:96
Case Time Limit:1000MS

Description

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

Input

第一行：三个整数，v(背包容量，v<=200),n（物品数量，n<=30)和t（最大组号，t<=10）;
第2…n+1行：每行三个整数wi,ci,p，表示每个物品的重量、价值、所属组号。

Output

仅一行，一个数，表示最大总价值。

Sample Input

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

Sample Output

20

思路

先将物品按组分类。
状态转移方程：
$1<=i<=T,v>=k>=1,1<=j<=l[i]$
$a=max(a,f[k-c[t[i][j]]]+w[t[i][j]])$
$f[k]=a$
$T表示组数，v表示背包容量，l[i]表示第i组的物品数$
枚举组，容量，并枚举组内物品找出其中价值最大数 —— $a$
再将 $a$ 赋值给$f[k]$

代码

#include<iostream>using namespace std;int v,n,t[211][211],w[211],c[211],p,T,l[211],a,f[211];void in(){   	//输入	scanf("%d%d%d",&v,&n,&T);	for(int i=1;i<=n;i++){   		scanf("%d%d%d",&c[i],&w[i],&p);		t[p][++l[p]]=i;//给该物品以组分类，且给该物品下标建链	}}void dp(){   	for(int i=1;i<=T;i++){   		for(int k=v;k>=1;k--){   			a=f[k];//赋初值			for(int j=1;j<=l[i];j++){   				if(k>=c[t[i][j]]) 				a=max(a,f[k-c[t[i][j]]]+w[t[i][j]]);//选出最大的价值			}f[k]=a;		}	} 	}int main(){   	in();	dp();	cout<<f[v];	return 0;}