※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

問い1092 Make KND So Fat

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1092
甘味どころで体重が増えるようにお菓子を買う問題。

解法
範囲が狭いので何も考えない動的計画法で十分解けます。


#include<stdio.h>
#include<vector>
void calc(int s,int d,int m){
	int memo[310]={0},k,w,p;;
	std::vector<int> ws[101],ps[101];
	for(int i=0;i<s;i++){
		scanf("%d",&k);
		for(int j=0;j<k;j++){
			scanf("%d %d",&w,&p);
			ws[i].push_back(w);
			ps[i].push_back(p);
		}
	}
	int f,a;
	for(int i=0;i<d;i++){
		scanf("%d",&f);
		for(int j=0;j<ws[f].size();j++){
			w=ws[f][j];
			p=ps[f][j];
			for(int k=m-p;k>=0;k--){
				if(k!=0&&memo[k]==0)continue;
				a=memo[k]+w;
				if(memo[k+p]<a)memo[k+p]=a;
			}
		}
	}
	int ansP=0,ansW=0;
	for(int i=0;i<=m;i++){
		if(ansW<memo[i]){
			ansW=memo[i];
			ansP=i;
		}
	}
	printf("%d %d\n",ansW,ansP);
} 

int main(){
	int s,d,m;
	while(scanf("%d",&s)!=EOF){
		scanf("%d %d",&d,&m);
		calc(s,d,m);
	}
}