0042 - A Thief

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

int dp[1000+1][1000+1];

int Slove(int W, int number)	{
	int N, value[1000], weight[1000], value_max=0, weight_max=0;

	cin >> N;
	for (int i=0; i<=N; ++i)
		for (int j=0; j<=W; ++j)
			dp[i][j]=0;
	for (int i=0; i<N; ++i)
		scanf ("%d,%d", &value[i], &weight[i]);
	for (int i=0; i<N; ++i)
		for (int j=0; j<=W; ++j)
			if ( j >= weight[i] )	dp[i+1][j]=max(dp[i][j],dp[i][ j-weight[i] ]+value[i]);
			else	dp[i+1][j]=dp[i][j];
	for (int j=0; j<=W; ++j)
		if ( value_max < dp[N][j] )	{
			value_max=dp[N][j];
			weight_max=j;
		}
	cout << "Case " << number++ << ":" << endl;
	cout << value_max << endl << weight_max << endl;
	return number;
}

int main(void)	{
	int W, number=1;

	while (cin >> W && W)
		number=Slove(W,number);
	return 0;
}

動的計画法のナップサック問題の典型。。