【SSL_2291】分組背包

分組背包

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 ] 1<=i<=T,v>=k>=1,1<=j<=l[i] 1<=i<=T,v>=k>=1,1<=j<=l[i]
a = m a x ( a , f [ k ? c [ t [ i ] [ j ] ] ] + w [ t [ i ] [ j ] ] ) a=max(a,f[k-c[t[i][j]]]+w[t[i][j]]) a=max(a,f[k?c[t[i][j]]]+w[t[i][j]])
f [ k ] = a f[k]=a f[k]=a
T 表 示 組 數 ， v 表 示 背 包 容 量 ， l [ i ] 表 示 第 i 組 的 物 品 數 T表示組數，v表示背包容量，l[i]表示第i組的物品數 T表示組數，v表示背包容量，l[i]表示第i組的物品數
列舉組，容量，并列舉組內物品找出其中價值最大數 —— a a a
再將 a a a 賦值給 f [ k ] f[k] 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;
}