AOJ_0042

ナップサック問題とくだけ。

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

const int MAX_N = 1000;
const int MAX_W = 1000;
int W, N;
int w[MAX_N + 1], v[MAX_N + 1];
int dp[MAX_N + 1][MAX_W + 1];
/*
dp[i][j] := i番目までの品物を重さj以下となるように選んだときの最大の価値
dp[0][j] := 0
dp[i][j] := max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
*/
int res;
int solve(){
	for(int i = 0; i <= W; i++)
		dp[0][i] = 0;
	for(int i = 1; i <= N; i++){
		for(int j = 0; j <= W; j++){
			if(0 > j - w[i])
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}
	int ans = dp[N][W];
	res = W;
	for(int i = 1; i <= N; i++)
		for(int j = 0; j <= W; j++)
			if(dp[i][j] == ans)
				res = min(res, j);
	return ans;
}
int main(){
	int count = 1;
	while(scanf("%d", &W)){
		if(W == 0) return 0;
		printf("Case %d:\n", count);
		scanf("%d", &N);
		for(int i = 1; i <= N; i++){
			scanf("%d, %d", &v[i], &w[i]);
		}
		printf("%d\n", solve());
		printf("%d\n", res);
		count++;
	}
	return 0;
}