AOJ0042

ソースコードの貼付けテストとして．

問題:A Thief
1年近く前に解いたナップザック問題．
初めて解いたDP．今ならもっときれいに書けると思う．

#include <iostream>
#include <map>
#include <vector>
#include <string.h>
#include <cstdio>
#include <set>
#define rep(i,n) for(i=0;i<n;++i)
using namespace std;
int main(){
	int i;
	int caseno = 0;
	int w,n,cost,weight;
	while( cin >> w , w ){
		cin >> n;
		vector <pair<int,int> >vp;
		rep(i,n){
			scanf("%d,%d",&cost,&weight);
			vp.push_back(pair<int,int> ( weight, cost) );
		}
		long dp[1001];//インデックス＝重さ 値＝価値
		long dp_[1001];
		rep(i,1001)dp[i]=-1;
		dp[0]=0;
		set<int> si,si_;
		si.insert(0);
		rep(i,n){
			si_ = si;
			memcpy(dp_,dp,sizeof(dp));
			for(set<int>::iterator it=si.begin(); it!=si.end() ; ++it){
				if( (*it+vp[i].first) > w )continue;
				dp_[*it+vp[i].first] = max( dp[*it+vp[i].first] , dp[*it]+vp[i].second );
				si_.insert(*it+vp[i].first);
			}
			memcpy(dp,dp_,sizeof(dp));
			si = si_;
		}
		map<long,int> mi;//<価値,重さ>
		//逆ループさせることで、同じ価値の場合は軽いほうで上書きされる
		for(i=w; i>=0; --i){
			if(dp[i]==-1)continue;
			mi[dp[i]] = i;
		}
		
		cout << "Case " << ++caseno << ":" << endl;
		cout << mi.rbegin()->first << endl;
		cout << mi.rbegin()->second << endl;
	}
	return 0;
}