AOJ 0042 A Thief

泥棒 | Aizu Online Judge

動的計画法の片鱗を味わった、二重for文でi番目の品物が重さjより軽ければ入れない場合と入れる場合で価値の高い方を選ぶ（dp[i-1][j-w[i]]≠0の時これまで入れた物との合計になる）

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

#define MAX 1001

int dp[MAX][MAX];
int v[MAX], w[MAX];

int main() {
	int W, n, u = 0;
	char t;
	while (cin >> W) {
		if (W == 0) break;
		cin >> n;
		u++;

		for (int i = 0; i < n; i++) {
			cin >> v[i] >> t >> w[i];
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= W; j++) {
				if (w[i - 1] <= j) {
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
				} else {
					dp[i][j] = dp[i - 1][j];
				}
			}
		}

		int mv, mw;
		mv = mw = 0;
		for (int i = 0; i <= W; i++) {
			if (dp[n][i] > mv) {
				mv = dp[n][i];
				mw = i;
			}
		}

		cout << "Case " << u << ":" << endl;
		cout << mv << endl;
		cout << mw << endl;
	}
	return 0;
}