[AtCoder] ABC 032 D – ナップサック問題

2020年12月12日

問題

方針

整数計画法である 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;
}