[AtCoder] ABC 032 D – ナップサック問題
問題
方針
整数計画法である 0-1 ナップサック問題を線形計画法で解くことを考えます。線形計画法では、重さ当たりの価値が大きいものから取っていけば良いです。ここで、荷物を重さ当たりの価値の降順になるように並び替えます。
深さ優先探索において、\( n – 1 \) 個まで選び方が確定しているとして、現在の探索までの価値の最大値を \( v^* \) とします。このとき選んだ荷物の価値を \( v \)、重さを \( w \) とします。\( n \) 個以降の荷物に対して線形計画法で解くことを考えます。許容量は \( W -w \) なので、
\[w_{n} + w_{n + 1} + \cdots + w_{l} \leq W – w\]
を満たす最大の \( l \) を求めます。線形計画法なので、価値は
\[ v + v_{n} + \cdots + v_{l} + (W – w – (w_n + \cdots w_{l}))\dfrac{v_{l + 1}}{w_{l + 1}}\]
となります。ここで、簡略化のために、
\begin{eqnarray}
w(l, r) &=& w_l + w_{l + 1} + \cdots + w_{r}\\
v(l, r) &=& v_l + v_{l + 1} + \cdots + v_{r}
\end{eqnarray}
と表記します。
\[ v + v(n, l) + (W – w – w(n, l)) \dfrac{v_{l + 1}}{w_{l + 1}} \leq v^{*}\]
を満たすとき、この探索を打ち切ります。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int N; ll W; pair<ll, ll> p[200]; // first: value, second: weight ll best = 0; ll s_v[201]{}, s_w[201]{}; // v_l + ... + v_{r - 1} ll sum_v(int l, int r) { return s_v[r] - s_v[l]; } // w_l + ... + w_{r - 1} ll sum_w(int l, int r) { return s_w[r] - s_w[l]; } void dfs(int n, ll v, ll w) { if (w > W) return; best = max(best, v); if (n == N || w == W) return; int l = n - 1; int r = N + 1; while (r - l > 1) { int m = l + (r - l) / 2; if (w + sum_w(n, m) <= W) { l = m; } else { r = m; } } if (l == N + 1 || W == w + sum_w(n, l)) { best = max(best, v + sum_v(n,l)); return; } else if (l == n - 1) { return; } else { ll _v = (v + sum_v(n, l)) * p[l].second + (W - w - sum_w(n, l)) * p[l].first; if (_v < best * p[l].second) return; } dfs(n + 1, v + p[n].first, w + p[n].second); dfs(n + 1, v, w); } int main() { cin >> N >> W; for (int i = 0; i < N; i++) { cin >> p[i].first >> p[i].second; } sort(p, p + N, [](auto const& o1, auto const& o2) { return o1.first * o2.second > o1.second * o2.first; }); for (int i = 0; i < N; i++) { s_v[i + 1] = s_v[i] + p[i].first; s_w[i + 1] = s_w[i] + p[i].second; } dfs(0, 0, 0); cout << best << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません