AtCoder ABC 060 D - Simple Knapsack (2Q, 水色, 400 点) (original) (raw)

面白い。各値に対する答えを予め整理して求めておく手法は頻出！

問題へのリンク

問題概要

$N$ 個の品物がある。品物 $i$ は、重さが $w_{i}$ であり、価値が $v_{i}$ である。

いくつかの品物を、総和が $W$ 以下となるように選ぶとき、選んだ品物の価値の総和の最大値を求めよ。

制約

$1 \le N \le 100$
$w_{1} \le w_{i} \le w_{1} + 3$

考えたこと

制約条件「 $w_{1} \le w_{i} \le w_{1} + 3$ 」が怪しい。つまり、重さは 4 種類しかないということだ。ということは、重さごとに品物を整理したくなる。そして、同じ重さであれば、価値が高いものから品物を選びたくなる。このような考察から、次の値を求めることができるだろう。

values[i][j]：重さが w[0] + i であるような品物を j 個選んだときの、価値の最大値（ $i = 0, 1, 2, 3$ ）

これを求めるのは簡単だ。単純に、重さが w[0] + i である品物について、その価値を大きい順にソートして、その累積和を求めれば良いのだ。

全探索

上記の配列 values が求まれば、次の全探索をすることで、答えが求められそうだ。

選んだとき、重さの総和が $W$ 以下である場合について、

values[0][i] + values[1][j] + values[2][k] + values[3][l]

の最大値を求めれば良いのだ。

最後に計算量を評価しよう。 $i, j, k, l$ のとりうる値の範囲は高々 $N+1$ 以下なので、上記解法の計算量は $O(N^{4})$ となる。十分間に合う。

コード

#include <bits/stdc++.h> using namespace std; const long long INF = 1LL << 60;

int main() { long long N, W, min_w = INF; cin >> N >> W; vector w(N), v(N); for (int i = 0; i < N; i++) cin >> w[i] >> v[i];

vector<vector<long long>> items(4);
for (int i = 0; i < N; i++) items[w[i]-w[0]].push_back(v[i]);
for (int i = 0; i < 4; i++) sort(items[i].begin(), items[i].end(), greater<long long>());


vector<vector<long long>> values(4);
for (int i = 0; i < 4; i++) {
    values[i].push_back(0);
    for (int j = 0; j < items[i].size(); j++) values[i].push_back(values[i].back() + items[i][j]);
}


long long res = 0;
for (int i = 0; i < values[0].size(); i++) {
    for (int j = 0; j < values[1].size(); j++) {
        for (int k = 0; k < values[2].size(); k++) {
            for (int l = 0; l < values[3].size(); l++) {
                long long weight = w[0] * i + (w[0]+1) * j + (w[0]+2) * k + (w[0]+3) * l;
                if (weight > W) continue;
                res = max(res, values[0][i] + values[1][j] + values[2][k] + values[3][l]);
            }
        }
    }
}
cout << res << endl;

}