概要

重量制限付きの0/1ナップサック問題に、\(K\) 個の「軽量化ケース」（アイテムの重さを半分にできる）という追加要素を加えた問題です。ナップサックDPに「使用したケース数」の次元を追加することで解きます。

考察

基本の観察

この問題は通常の0/1ナップサック問題の拡張です。軽量化ケースがなければ、\(dp[c] = \) 重量 \(c\) 以内で得られる最大価値、という標準的なDPで解けます。

素朴なアプローチの問題

軽量化ケースを「どの宝石に使うか」を全探索すると、\(N\) 個から \(K\) 個を選ぶ組み合わせ \(\binom{N}{K}\) 通りがあり、\(K\) が大きい場合は膨大になります。

解決策

\(K \leq 30\) と小さいことに着目し、DPの状態に「今まで使ったケースの個数」を追加します。すなわち：

\[dp[k][c] = \text{ケースを } k \text{ 個使い、総重量が } c \text{ 以内のときの最大価値}\]

各宝石について「ケースを使って入れる」「ケースを使わず入れる」「入れない」の3択を考えます。

アルゴリズム

1. \(dp[k][c]\) を全て \(0\) で初期化する（\(0 \leq k \leq K\), \(0 \leq c \leq C\)）。

2. 各宝石 \(i\) について、0/1ナップサックと同様に逆順ループで更新する：

   • \(k\) を \(K\) から \(0\) まで逆順に走査
   • \(c\) を \(C\) から \(0\) まで逆順に走査
   • ケースを使って入れる場合（\(k > 0\) かつ \(c \geq \lfloor W_i/2 \rfloor\)）： $\(dp[k][c] = \max(dp[k][c],\ dp[k-1][c - \lfloor W_i/2 \rfloor] + B_i)\)$
   • ケースを使わず入れる場合（\(c \geq W_i\)）： $\(dp[k][c] = \max(dp[k][c],\ dp[k][c - W_i] + B_i)\)$

3. 全ての \(dp[k][c]\) の最大値が答え。

なぜ逆順ループで正しいか

0/1ナップサックの標準テクニックです。\(c\) と \(k\) を大きい方から更新することで、同じアイテムを2回以上選ぶことを防ぎます。「ケースを使って入れる」遷移は \(dp[k-1][\cdot]\) から \(dp[k][\cdot]\) への遷移であり、\(k\) を降順に処理しているため、まだ今の宝石を考慮していない状態から値を参照できます。

計算量

• 時間計算量: \(O(N \cdot (K+1) \cdot (C+1))\)
  • 制約より \(N(K+1)(C+1) \leq 2 \times 10^7\) が保証されている
• 空間計算量: \(O((K+1) \cdot (C+1))\)

実装のポイント

• DPテーブルを2次元配列ではなく1次元配列（サイズ \((K+1) \times (C+1)\)）として確保し、ポインタ演算でアクセスすることでキャッシュ効率を向上させている。

• 価値 \(B_i\) が最大 \(10^9\) で \(N\) が最大 \(10^5\) なので、合計値は long long 型が必要。

• 「ケースを使って入れる」遷移では dp[k-1] の行を参照するため、\(k=0\) のときは実行しないようガードが必要。

• \(W_i\) が最大 \(2C\) まであり得るので、軽量化ケースを使わないと容量に入りきらない宝石が存在する点に注意。

  ソースコード

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

int main() {
    int N, C, K;
    scanf("%d %d %d", &N, &C, &K);
    
    vector<int> B(N), W(N);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &B[i], &W[i]);
    }
    
    int cols = C + 1;
    int sz = (K + 1) * cols;
    vector<long long> dp(sz, 0);
    
    for (int i = 0; i < N; i++) {
        int w = W[i];
        int wh = W[i] / 2;
        long long b = B[i];
        
        for (int k = K; k >= 0; k--) {
            long long* cur = dp.data() + (long long)k * cols;
            long long* prev = (k > 0) ? dp.data() + (long long)(k - 1) * cols : nullptr;
            
            for (int c = C; c >= 0; c--) {
                // Take with case
                if (k > 0 && c >= wh) {
                    long long val = prev[c - wh] + b;
                    if (val > cur[c]) cur[c] = val;
                }
                // Take without case
                if (c >= w) {
                    long long val = cur[c - w] + b;
                    if (val > cur[c]) cur[c] = val;
                }
            }
        }
    }
    
    long long ans = 0;
    for (int j = 0; j < sz; j++) {
        if (dp[j] > ans) ans = dp[j];
    }
    
    printf("%lld\n", ans);
    return 0;
}

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