泥棒 | Aizu Online Judge
int main() {
int cas = 1;
while (1) {
int N, W;
int v[1005], w[1005], dp[1005][1005];
cin >> W; if (!W) break;
cin >> N;
for (int i = 0; i < N; i++) {
char c;
cin >> v[i] >> c >> w[i];
}
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
int res = 0, resw = 1000*1000*1000*2;
for (int i = 0; i < N; i++) {
for (int j = 0; j <= W; j++) {
if (j - w[i] >= 0) {
dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j]);
} else {
dp[i + 1][j] = dp[i][j];
}
if (dp[i+1][j] == -1) continue;
if (dp[i + 1][j] > res) {
res = dp[i + 1][j];
resw = j;
} else if (dp[i + 1][j] == res) {
resw = min(resw, j);
}
}
}
cout << "Case " << cas << ":" << endl;
cout << res << endl;
cout << resw << endl;
cas++;
}
return 0;
}