AtCoder蟻本 初級編 2-3 動的計画法 ①01ナップサック問題
AOJ DPL_1_B 0-1 ナップザック問題
ナップザック問題 | 動的計画法 | Aizu Online Judge
概要
重さ、価値の荷物が個ある。
重さの合計が以内になるように荷物を選んだ時、荷物の価値の合計の最大値を求めよ。
制約
方針
番目までの荷物を使い、重さが以内であるときの価値の最大値
という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++){ dp[i+1][j] = dp[i][j]; if(j - w[i] >= 0) { dp[i+1][j] = max(dp[i][j], dp[i][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; }