AtCoder蟻本 初級編 2-3 動的計画法 ③個数制限なしナップサック問題

AOJ DPL1_C ナップザック問題

概要

重さ、価値の荷物が個ある。
重さの合計が以内になるように荷物を選んだ時、荷物の価値の合計の最大値を求めよ。
ただし、同じ荷物を何度選んでもよい。

制約

方針

番目までの荷物を使い、重さが以内であるときの価値の最大値
というDPで計算する。
という算式が必要だが、
これはとおくと、のループで全て計算される。

解答

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, max_w;
	cin >> n >> max_w;

	int v[n], w[n];
	rep(i, n) cin >> v[i] >> w[i];

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

	ll ans = 0;
	for(int i = 0; i <= max_w; i++){
		ans = max(ans, dp[n][i]);
	}
	cout << ans << endl;
}