DPまとめコンテスト E - Knapsack 2

E - Knapsack 2

概要

個の品物があり、品物の重さが、価値がであるとする。
それぞれの品物高々1つナップサックに詰める。ナップサックに入れる品物の重さの総和を以下とするとき、
ナップサックに詰める品物の価値の総和の最大値を求めよ。

制約

方針

dp[i] : 価値iを作れるときの重さの最小値 とし、DPする。

解答

Submission #3941419 - Educational DP Contest / 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;
 
	ll w[n], v[n];
	rep(i, n) cin >> w[i] >> v[i];
 
	ll INF = 1e13;
	ll max_v = 100000;
	ll dp[max_v+1];
	// dp[i] : 価値iを作れるときの重さの最小値
	for(int i = 0; i <= max_v; i++){
		dp[i] = INF;
	}
 
	dp[0] = 0;
	for(int i = 1; i <= n; i++){
		for(int j = max_v; j >= 0; j--){
			if(j - v[i-1] >= 0) dp[j] = min(dp[j], dp[j - v[i-1]] + w[i-1]);
		}
	}
 
	ll ans = 0;
	for(int i = 0; i <= max_v; i++){
		if(dp[i] <= max_w) ans = max(ans, (ll)i);
	}
 
	cout << ans << endl;
}