概要

各宝石について「選ばない」「そのまま選ぶ」「軽量化ケースを使って選ぶ」の 3 通りを考える、ナップサック問題です。

軽量化ケースの使用個数も状態に持つ動的計画法で、価値の合計の最大値を求めます。

考察

通常の 0/1 ナップサックでは、各品物について「選ぶ / 選ばない」を考えます。

この問題では、宝石 \(i\) を選ぶ場合にさらに次の 2 通りがあります。

• そのまま選ぶ
  
  • 重さ \(W_i\)
  • ケースを使わない
• 軽量化して選ぶ
  
  • 重さ \(\left\lfloor \frac{W_i}{2} \right\rfloor\)
  • ケースを 1 個使う

ただし、同じ宝石に複数個のケースは使えず、各宝石は高々 1 個しか選べません。

例えば、単純に「通常版の宝石」と「軽量化版の宝石」を別々の品物としてナップサックに入れてしまうと、同じ宝石を通常版と軽量化版の両方で選べてしまうため誤りです。

そこで、各宝石を 1 つずつ処理しながら、

• 今までに何個までケースを使ったか
• 現在の重量上限がいくつか

を状態として持つ DP を行います。

アルゴリズム

\(dp[j][c]\) を次のように定義します。

これまでに処理した宝石について、軽量化ケースを高々 \(j\) 個使い、総重量を \(c\) 以下にしたときの価値の最大値

ここで「ちょうど \(j\) 個」ではなく「高々 \(j\) 個」とするのがポイントです。ケースは余ってもよいからです。

宝石の価値を \(b\)、重さを \(w\)、軽量化後の重さを

\[ h = \left\lfloor \frac{w}{2} \right\rfloor \]

とします。

この宝石に対して、遷移は次の 3 通りです。

1. 選ばない

何もしません。

\[ dp[j][c] \]

はそのまま残ります。

2. そのまま選ぶ

ケースを使わず、重さ \(w\) を消費します。

\[ dp[j][c] = \max(dp[j][c], dp[j][c-w] + b) \]

ただし、\(c \geq w\) のときだけ可能です。

3. 軽量化して選ぶ

ケースを 1 個使い、重さ \(h\) を消費します。

\[ dp[j][c] = \max(dp[j][c], dp[j-1][c-h] + b) \]

ただし、\(j \geq 1\) かつ \(c \geq h\) のときだけ可能です。

例えば、重さ \(w=7\) の宝石は軽量化すると \(h=3\) になります。

• 容量 \(c=5\) のとき
  
  • 通常の重さ \(7\) では入らない
  • 軽量化すれば重さ \(3\) なので入る
• 容量 \(c=8\) のとき
  
  • 通常でも入る
  • 軽量化しても入る

このように、容量によって可能な選び方が変わります。

DP の更新では、各宝石を 1 回しか使えないようにするため、次の順でループします。

• ケース数 \(j\) は大きい方から小さい方へ
• 重量 \(c\) も大きい方から小さい方へ

これにより、同じ宝石を複数回使ってしまうことを防げます。

最終的な答えは、容量 \(C\)、ケースを高々 \(K\) 個使える場合の値なので、

\[ dp[K][C] \]

です。

コードでは、まだ到達し得ないケース数の行を作らないように、active で現在使う DP 行数を管理しています。

計算量

• 時間計算量: \(O(NKC)\)
• 空間計算量: \(O(KC)\)

制約で

\[ N(K+1)(C+1) \leq 2 \times 10^7 \]

が保証されているため、この計算量で十分間に合います。

実装のポイント

• dp[j][c] は「ケースを高々 \(j\) 個使う」として持ちます。

• 軽量化後の重さは h = w >> 1 で計算しています。これは \(\left\lfloor \frac{w}{2} \right\rfloor\) と同じです。

• \(j\) と \(c\) を降順に更新することで、同じ宝石を複数回選ぶことを防ぎます。

• \(W_i > C\) の宝石は、そのままでは絶対に入らないため、軽量化して選ぶ遷移だけを行います。

• 価値 \(B_i\) は最大 \(10^9\) で、合計は大きくなる可能性があるため、C++ なら long long が必要です。Python では通常の int で問題ありません。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, C, K = data[0], data[1], data[2]

    dp = [None] * (K + 1)
    dp[0] = [0] * (C + 1)

    active = 0
    idx = 3

    for _ in range(N):
        b = data[idx]
        w = data[idx + 1]
        idx += 2
        h = w >> 1

        if active < K:
            na = active + 1
            dp[na] = dp[active].copy()
        else:
            na = active

        if w <= C:
            ww = w
            hh = h

            for j in range(na, 0, -1):
                row = dp[j]
                prev = dp[j - 1]

                for c in range(C, ww - 1, -1):
                    x = row[c - ww]
                    y = prev[c - hh]
                    if y > x:
                        x = y
                    x += b
                    if x > row[c]:
                        row[c] = x

                for c in range(ww - 1, hh - 1, -1):
                    x = prev[c - hh] + b
                    if x > row[c]:
                        row[c] = x

            row = dp[0]
            for c in range(C, ww - 1, -1):
                x = row[c - ww] + b
                if x > row[c]:
                    row[c] = x
        else:
            hh = h
            for j in range(na, 0, -1):
                row = dp[j]
                prev = dp[j - 1]
                for c in range(C, hh - 1, -1):
                    x = prev[c - hh] + b
                    if x > row[c]:
                        row[c] = x

        active = na

    print(dp[active][C])

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。