AtCoder蟻本 初級編 2-3 動的計画法 ④01ナップサック問題その２

ABC032 D - ナップサック問題

D - ナップサック問題

概要

• 0/1ナップサック
• 制約が3種類

制約

①

②

③

方針

実質３問。
①
いわゆる半分全列挙。
荷物を前半分、後半分の２つに分け、それぞれですべての荷物の入れ方で重さの合計、価値の合計のペアをベクトルに格納する。
前半分の荷物で作成したベクトルをv1、後半分をv2とする。

その後、v1の要素を1つずつ取り出し、v2の要素の中で、
「両者の重さの合計が以下で価値が最大のもの」を探す。
全てのv1の要素でそれを行い、価値が最大のものが答え。

探し方は愚直にやるとO(v1.size * v2.size)だが、ソートしてv1を重い方から、v2を軽い方から見てゆくとO(max(v1.size, v2.size))になる（はず）。

②
の上限が小さいので、dp[i] : 重さ合計がiのときにできる価値合計の最大値としてDPする。

③
の上限が小さいので、dp[i] : 価値合計がiのときにできる重さ合計の最小値としてDPする。

感想

下記解答を参考にしました。
Submission #1381183 - AtCoder Beginner Contest 032

②、③はdp[i][j]のように2次元で組むとセグフォする（メモリオーバー？）。
1次元DPでやるときは、dp[i]をiが大きい方から遷移させると、同じ荷物で何度も更新することがない。
逆に同じ荷物で何度も更新したい場合はdp[i]をiが小さい方から遷移させる。

解答

Submission #1381183 - AtCoder Beginner Contest 032

#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;
typedef pair<ll, ll> pll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n, max_w;
	cin >> n >> max_w;
 
	ll v[n], w[n];
	rep(i, n) cin >> v[i] >> w[i];
 
	ll mv = 0;
	ll mw = 0;
	rep(i, n){
		mv = max(mv, v[i]);
		mw = max(mw, w[i]);
	}
 
	if(n <= 30){
		if(n == 1){
			cout << (w[0] <= max_w ? v[0] : 0) << endl;
			return 0;
		}
 
		int n1 = n / 2;
		int n2 = n - n1;
 
		vector<pll> v1, v2;
		for(ll i = 0; i < (1 << n1); i++){
			ll tv = 0;
			ll tw = 0;
			for(ll j = 0; j < n1; j++){
				if((i >> j) & 1){
					tv += v[j];
					tw += w[j];
				}
 
				if(tw <= max_w){
					// cout << "push1: " << tw << " " << tv << endl;
					v1.push_back((pll){tw, tv});
				}
			}
		}
 
		for(ll i = 0; i < (1 << n2); i++){
			ll tv = 0;
			ll tw = 0;
			for(ll j = n1; j < n1 + n2; j++){
				if((i >> (j - n1)) & 1){
					tv += v[j];
					tw += w[j];
				}
 
				if(tw <= max_w){
					// cout << "push2: " << tw << " " << tv << endl;
					v2.push_back((pll){tw, tv});
				}
			}
		}
 
		sort(v1.begin(), v1.end());
		sort(v2.begin(), v2.end());
 
		ll m1 = v1.size();
		ll m2 = v2.size();
		ll ans = 0LL;
		ll ma = 0LL;
		ll j = 0LL;
		for(ll i = m1-1; i >= 0; i--){
			pll p1 = v1[i];
			while(j < m2 && p1.first + v2[j].first <= max_w){
				// if(p1.second + v2[j].second > ans) cout << p1.first << " " << p1.second << " " << v2[j].first << " " << v2[j].second << endl;
				ma = max(ma, v2[j].second);
				j++;
			}
			ans = max(ans, p1.second + ma);
		}
 
		cout << ans << endl;
		return 0;
 
	}else if(mv <= 1000){
 
		ll INF = 1e15;
		mv = 200010;
 
		ll dp2[mv+1];
		rep(j, mv+1) dp2[j] = INF;
		dp2[0] = 0;
 
		for(int i = 0; i < n; i++){
			for(int j = mv; j >= 0; j--){
				if(j - v[i] >= 0){
					dp2[j] = min(dp2[j], dp2[j-v[i]]+w[i]);
				}
			}
		}
 
		for(ll i = mv; i >= 0; i--){
			if(0 <= dp2[i] && dp2[i] <= max_w){
				cout << i << endl;
				return 0;
			}
		}
	}else{
		ll INF = 1e15;
		mw = 200010;
		ll dp3[mw+1];
		rep(j, mw+1) dp3[j] = 0;
		for(int i = 0; i < n; i++){
			for(int j = mw; j >= 0; j--){
				if(j - w[i] >= 0){
					dp3[j] = max(dp3[j], dp3[j-w[i]]+v[i]);
				}
			}
		}
 
		ll ans = 0;
		for(ll i = 0; i <= max_w; i++){
			ans = max(ans, dp3[i]);
		}
 
		cout << ans << endl;
	}
}