概要

重量制限付きの0/1ナップサック問題に「\(K\)個の軽量化ケースで宝石の重さを半減できる」という追加条件が加わった問題です。ケースの使用個数を追加次元としたDPで解きます。

考察

基本的な気づき

この問題は通常の0/1ナップサック問題の拡張です。各宝石に対して以下の3つの選択肢があります：

1. 持ち込まない
2. そのまま持ち込む（重さ \(W_i\)）
3. 軽量化ケースを使って持ち込む（重さ \(\lfloor W_i / 2 \rfloor\)、ケースを1個消費）

素朴なアプローチの問題

単純に「どの宝石にケースを使うか」を全探索すると \(\binom{N}{K}\) 通りあり、\(N\) が大きい場合に爆発します。

解決方針

ケースの使用個数を状態に組み込んだDPを行います。\(dp[k][c]\) を「軽量化ケースを \(k\) 個まで使い、総重量 \(c\) 以内で得られる最大価値」と定義すれば、各宝石を1つずつ処理する標準的なナップサックの要領で解けます。

アルゴリズム

DP定義

\[dp[k][c] = \text{ケースを最大 } k \text{ 個使い、容量 } c \text{ 以内で得られる最大価値}\]

遷移

各宝石 \((B_i, W_i)\)（半減重量 \(hw_i = \lfloor W_i/2 \rfloor\)）に対して、\(k\) を \(K\) から \(0\) まで、\(c\) を \(C\) から降順に走査し：

• そのまま持ち込む（\(c \geq W_i\) のとき）： $\(dp[k][c] \leftarrow \max(dp[k][c],\ dp[k][c - W_i] + B_i)\)$

• ケースを使って持ち込む（\(k > 0\) かつ \(c \geq hw_i\) のとき）： $\(dp[k][c] \leftarrow \max(dp[k][c],\ dp[k-1][c - hw_i] + B_i)\)$

\(k\) と \(c\) を降順に処理することで、同じ宝石を複数回選ぶことを防ぎます（0/1ナップサックの標準テクニック）。

具体例

例：\(N=2, C=10, K=1\)、宝石1: \((B=100, W=8)\)、宝石2: \((B=80, W=6)\)

• 宝石1にケースを使うと重さ4に → 宝石1(重さ4) + 宝石2(重さ6) = 重さ10で価値180
• ケースなしでは重さ8+6=14 > 10 で両方は持てない

DPが最適な割り当てを自動的に見つけます。

計算量

• 時間計算量: \(O(N \cdot (K+1) \cdot C)\)
  • 制約 \(N(K+1)(C+1) \leq 2 \times 10^7\) により実行時間内に収まる
• 空間計算量: \(O((K+1) \cdot C)\)

実装のポイント

1. 降順ループ: 0/1ナップサックなので、容量 \(c\) もケース数 \(k\) も大きい方から更新します。これにより同じアイテムを重複選択することを防ぎます。

2. 場合分けによる高速化: \(W_i > C\) の場合、ケースなしでは絶対に入らないため、ケース使用の遷移のみを行います。また、\(W_i \leq C\) の場合でも、\(hw_i \leq c < W_i\) の範囲ではケース使用の遷移のみが有効なので、ループを分割して無駄な比較を減らしています。

3. ビットシフト: \(\lfloor W_i / 2 \rfloor\) を w >> 1 で計算し、わずかに高速化しています。

4. Python での速度対策: sys.stdin.buffer.read() で入力を一括読み込みし、DPテーブルの行を変数（dpk, dpk1）に束縛することで属性アクセスのオーバーヘッドを削減しています。

   ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    C = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    items = []
    for i in range(N):
        b = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        items.append((b, w))
    
    # dp[k][c] = max value using at most k cases, weight at most c
    dp = [[0] * (C + 1) for _ in range(K + 1)]
    
    for b, w in items:
        hw = w >> 1
        for k in range(K, -1, -1):
            dpk = dp[k]
            if k > 0:
                dpk1 = dp[k - 1]
                if w <= C:
                    for c in range(C, w - 1, -1):
                        val = dpk[c]
                        nv = dpk[c - w] + b
                        if nv > val:
                            val = nv
                        nv = dpk1[c - hw] + b
                        if nv > val:
                            val = nv
                        dpk[c] = val
                    upper = min(w - 1, C)
                    for c in range(upper, hw - 1, -1):
                        nv = dpk1[c - hw] + b
                        if nv > dpk[c]:
                            dpk[c] = nv
                else:
                    if hw <= C:
                        for c in range(C, hw - 1, -1):
                            nv = dpk1[c - hw] + b
                            if nv > dpk[c]:
                                dpk[c] = nv
            else:
                if w <= C:
                    for c in range(C, w - 1, -1):
                        nv = dpk[c - w] + b
                        if nv > dpk[c]:
                            dpk[c] = nv
    
    print(dp[K][C])

main()

---

この解説は claude4.6opus-thinking によって生成されました。