けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 本選 2012 C - 夜店 (AOJ 0573, 難易度 6)

左右からナップサックした結果を前処理する系! (他の解法もあり)

問題概要 (意訳) (実際の問題文は時刻に関する問題)

 N 個の品物がある。それぞれ  1, 2, \dots, N の番号がついている。番号が  i の品物は

  • 価値が  A_{i}
  • 重さが  B_{i}

となっている。これらを 2 つのナップサック P, Q に詰めたい。ナップサック P, Q に詰められる品物の重さの合計は、それぞれ  S,  T-S 以下である ( T は 2 つのナップサックの容量の合計値)。

品物を詰めるとき、ナップサック P に入っている任意の品物の番号は、 ナップサック Q に入っている任意の品物の番号よりも小さくなければならない。

2 つのナップサックに入っている品物の価値の合計値の最大値を求めよ。

制約

  •  1 \le N \le 3000
  •  1 \le S \le T \le 3000

解法 (1):左右からナップサック

ナップサックが 1 個だけならば、完全にナップサック問題そのものである。しかしナップサックが 2 個になっても問題はそれほど変わらない。

注意しなければならないのは、「1 個目のナップサックの番号は 2 個目のナップサックの番号よりもすべて若い」という条件を満たすようにすることだ。そこで、次のようにする

  • left[ i ][ w ] := 左から i 個分の品物のみを考えたときの、選んだ品物の総和が w 以下となるようにしたときの、価値の総和の最大値
  • right[ i ][ w ] := 右から i 個分の品物のみを考えたときの、選んだ品物の総和が w 以下となるようにしたときの、価値の総和の最大値

これらは普通にナップサック DP をすれば OK。これらの結果があれば、次のように最適解が求められる。


各 i = 0, 1, ..., N について

left[ i ][ S ] + right[ N - i ][ T - S ]

を求めて、その最大値をとる


計算量は  O(NT)

#include <bits/stdc++.h>
using namespace std;

const int INF = 1<<29;
int main() {
    int N, T, S;
    cin >> N >> T >> S;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];

    auto add = [&](vector<int> dp, int a, int b) -> vector<int> {
        for (int t = T; t >= b; --t) dp[t] = max(dp[t], dp[t-b]+a);
        return dp;
    };

    vector<vector<int>> left(N+1, vector<int>(T+1, -INF)), right = left;
    for (int t = 0; t <= T; ++t) left[0][t] = right[0][t] = 0;
    for (int i = 0; i < N; ++i) {
        left[i+1] = add(left[i], A[i], B[i]);
        right[i+1] = add(right[i], A[N-i-1], B[N-i-1]);
    }
    int res = 0;
    for (int l = 0; l <= N; ++l) {
        res = max(res, left[l][S] + right[N-l][T-S]);
    }
    cout << res << endl;
}

解法 (2):上手にナップサック (olverx 君より!)

普通のナップサックでも、うまくやれば解ける!

  • dp[ i ][ w ] := 左から i 個分の品物のみを考えたときの、選んだ品物の総和が w となるようにしたときの、価値の総和の最大値

として、

「w (<= S) にアイテムを追加すると S を超えてしまうようなときは、S の状態から追加するようにする」

というふうにすれば OK。この場合も計算量は  O(NT) となる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF = 1<<29;
int main() {
    int N, T, S;
    cin >> N >> T >> S;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];

    vector<vector<int>> dp(N+1, vector<int>(T+1, -INF));
    dp[0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int t = 0; t <= T; ++t) {
            chmax(dp[i+1][t], dp[i][t]);
            int t2 = (t <= S && t+B[i] > S ? S+B[i] : t+B[i]);
            if (t2 <= T) chmax(dp[i+1][t2], dp[i][t] + A[i]);
        }
    }
    int res = 0;
    for (int t = 0; t <= T; ++t) chmax(res, dp[N][t]);
    cout << res << endl;
}