Educational DP Contest D - Knapsack 1

問題

atcoder.jp

問題概要

N個の品物があり、i番目(1-index)の品物の品物の重さはw[i-1]で、価値はv[i-1]である。
品物を重さの合計がWを超えないように選ぶとき価値の総和の最大値を求めよ。

解法

ナップサックDPである。

dp[i][j] : i番目まで見て重さの合計がjを超えないように選んだときの価値の合計の最大値
0≦i≦N , 0≦j≦W

i番目の品物を選ぶか選ばないかの2通りがある。

i番目の品物を選ばないとき
dp[i][j]=dp[i-1][j]

i番目の品物を選ぶとき
dp[i][j]=dp[i-1][j-w[i-1]]+v[i-1]

dp[i][j]はこれらのうち大きいほうである。
しかしj-w[j-1]<0の時は配列外参照になるので
dp[i][j]=dp[i-1][j]
になる。

i=0の時は何も選んでいないのでdp[i][j]は0になる。

ソースコード

signed main() {
	int N, W;
	cin >> N >> W;
	vector<int>w(N);
	vector<int>v(N);
	rep(i, N) {
		cin >> w[i] >> v[i];
	}
	vector<vector<int>>dp(N + 1, vector<int>(W + 1));
	rep(i, N + 1) {
		rep(j, W + 1) {
			if (i == 0) {
				dp[i][j] == 0;
			}
			else {
				if (j - w[i - 1] < 0) {
					dp[i][j] = dp[i - 1][j];
				}
				else {
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
				}
			}
		}
	}
	cout << dp[N][W] << endl;
}