PKU 3497-Assemble

問題概要

コンピューターを組み立てたい．
部品にはその種類とその価値およびその価格が与えられる．
コンピューターを組み立てるとき，その全体の価値は各部品の価値の最小値になる．また全ての種類の部品を一つずつ用いて組み立てなければいけない．
財布に入っているお金が作れるコンピューターの価値を最大化しろ

解法

最大の価値は各部品の価値のどれかの値を取る．
よって，各部品の価値について，それ以上の価値の最小の値段の部品を貪欲に選んでいった時の金額を計算し，bを超えないか考えれば良い．

実装(C++)

#include <algorithm>
#include <vector>
#include <iostream>
#include <cstdio>
using namespace std;

typedef int lli;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define rep(i,s,x) for(int i=s;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
int n;lli b;
int k;
string type[1000];
typedef pair<lli,lli> P;
vector<P> data[1000];
char tmpin[1000];
int kh[1001];
int khc;
int solve(int q,int MIN){
	int tmp=0;
	for(int i=0;i<k;i++){
		bool ok=false;
		REP(j,data[i].size()){
			if(data[i][j].second>=MIN){
				tmp+=data[i][j].first;
				ok=true;
				break;
			}
		}
		if(!ok)return false;
		if(tmp>b)return false;
	}
	return true;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&b);
		k=0;khc=0;
		REP(i,n){
			string tn,nm;
			scanf("%s",tmpin);
			tn=string(tmpin);
			scanf("%s",tmpin);
			nm=string(tmpin);

			int b=find(type,type+k,tn)-type;
			if(b==k){
				data[k].clear();
				type[k]=tn;
				k++;
			}
			P t;
			scanf("%d%d",&t.first,&t.second);
			data[b].push_back(t);
			kh[khc++]=t.second;
		}
		for(int i=0;i<k;i++)std::sort(data[i].begin(),data[i].end());
		std::sort(kh,kh+khc);
		reverse(kh,kh+khc);
		bool ans=false;
		for(int i=0;i<khc;i++){
			if(solve(0,kh[i])){
				cout<<kh[i]<<endl;
				ans=true;
				break;
			}
		}
		if(ans==false){
			cout<<0<<endl;
		}
	}
}