A Thief

泥棒 | 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;
}