問題概要

$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[0] である品物を $i$ 個 ( $i = 0, 1, \dots$ )
重さが w[0] + 1 である品物を $j$ 個 ( $j = 0, 1, \dots$ )
重さが w[0] + 2 である品物を $k$ 個 ( $k = 0, 1, \dots$ )
重さが w[0] + 3 である品物を $l$ 個 ( $l = 0, 1, \dots$ )

選んだとき、重さの総和が $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<long long> 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>());

    // 重さごとに、n 個とる価値の総和の最大値を求めていく
    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;
}