A Thief
コード

ただのナップサック問題。だったので、紙を使わずに暗算で漸化式を立てて解きました。

dp[j][i] = i個目までの美術品をjの重さで盗んだ時の価値の最大値
初期状態は、dp[j][0] = 0 for all j
漸化式は、dp[j][i] = max(dp[j][i], dp[j-w][i]))で更新。

#include <iostream>
#include <algorithm>
#include <stdio.h>
 
using namespace std;
 
#define WMAX 1000
#define NMAX 1000
int main(void)
{
    int W, n;
    int cyc = 0;
    while (cin >> W && W && cin >> n) {
        cyc++;
        int dp[WMAX+1][NMAX+1] = {};
        for (int i = 0; i < n; i++) {
            int v, w;
            scanf("%d,%d", &v, &w);
            for (int j = 0; j < W+1; j++) 
                dp[j][i+1] = max(dp[j][i], (j-w >= 0 ? dp[j-w][i] + v : 0));
        }
        cout << "Case " << cyc << ":" << endl;
        for (int j = 0; j < W+1; j++) {
            if (dp[j][n] == dp[W][n]) {
                cout << dp[j][n] << endl << j << endl;
                break;
            }
        }
    }
}