概要

\(N\) 種類の紐（各種類に在庫数制限あり）から何本かを選び、長さの合計がちょうど \(W\) になるようにしつつ、使用本数を最小化する問題です。これは「個数制限付きナップサック問題」の一種です。

考察

問題の本質

各種類の紐 \(i\) は長さ \(L_i\) で \(C_i\) 本まで使えます。合計長さをちょうど \(W\) にしながら、使う本数を最小にしたいです。これは典型的な個数制限付きナップサック問題（Bounded Knapsack Problem）です。

素朴なアプローチとその問題点

アプローチ1: 1本ずつ扱う 各種類の紐 \(i\) を \(C_i\) 本の個別アイテムとして扱い、0-1 ナップサックを解く方法が考えられます。しかし \(C_i\) は最大 \(10000\)、\(N\) は最大 \(100\) なので、アイテム総数は最大 \(100 \times 10000 = 10^6\) になります。各アイテムについて \(O(W)\) の更新が必要なので、\(O(10^6 \times 50000) = O(5 \times 10^{10})\) となり、到底間に合いません。

アプローチ2: 完全ナップサック風 在庫制限を無視して無制限に使えるとすれば完全ナップサック問題ですが、本問では在庫制限があるため正しく解けません。

解決策：二進分割（Binary Splitting）

個数制限 \(C_i\) を二進数の各桁に対応するグループに分割するテクニックを使います。

例えば \(C_i = 13\) のとき、\(13 = 1 + 2 + 4 + 6\) と分割します（\(1, 2, 4\) は \(2\) のべき乗、\(6\) は残り）。これらのグループを組み合わせることで、\(0\) 本から \(13\) 本までの任意の本数を表現できます。

こうすると \(C_i\) 本のアイテムが \(O(\log C_i)\) 個のグループに圧縮され、各グループに対して 0-1 ナップサックの更新を行えばよくなります。

アルゴリズム

1. DP配列の初期化: \(dp[w]\) を「長さの合計がちょうど \(w\) となる最小本数」とし、\(dp[0] = 0\)、それ以外を \(\infty\) に初期化します。

2. 各種類の紐について二進分割: 種類 \(i\) の在庫 \(C_i\) を \(1, 2, 4, 8, \ldots\) のグループに分割します。例えば \(C_i = 13\) なら \(\{1, 2, 4, 6\}\) に分割。

3. 各グループについて 0-1 ナップサック更新: グループの本数を \(c\) とすると、「重さ \(L_i \times c\)、コスト \(c\)」の単一アイテムとみなし、\(w = W\) から \(L_i \times c\) まで逆順にループして更新します： $\(dp[w] = \min(dp[w],\ dp[w - L_i \times c] + c)\)$

4. 結果の出力: \(dp[W]\) が \(\infty\) なら \(-1\)、そうでなければ \(dp[W]\) を出力。

計算量

• 時間計算量: \(O(N \cdot W \cdot \log C_{\max})\)
  • 各種類あたりグループ数は \(O(\log C_i)\) 個、各グループの更新に \(O(W)\)
  • \(N = 100\), \(W = 50000\), \(\log_2(10000) \approx 14\) で約 \(7 \times 10^7\) 程度
• 空間計算量: \(O(W)\)（DP配列のサイズ）

実装のポイント

• 二進分割の実装: \(k = 1, 2, 4, \ldots\) と倍にしながら、残りの本数 remaining から min(k, remaining) を取ってグループを作ります。最後のグループが \(2\) のべき乗でない端数になるのがポイントです。

• 0-1 ナップサックの逆順ループ: 各グループを「1つのアイテム」として扱うため、同じグループを重複使用しないよう \(w\) を大きい方から更新します。

• weight = L * count が \(W\) を超える場合はスキップすることで、無駄な計算を避けます。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    W = int(input_data[idx]); idx += 1
    
    items = []
    for i in range(N):
        L = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        items.append((L, C))
    
    INF = float('inf')
    # dp[w] = minimum number of strings to make exactly w cm
    dp = [INF] * (W + 1)
    dp[0] = 0
    
    # Bounded knapsack with binary splitting
    for L, C in items:
        # Split C into powers of 2
        groups = []
        remaining = C
        k = 1
        while remaining > 0:
            take = min(k, remaining)
            groups.append(take)
            remaining -= take
            k *= 2
        
        for count in groups:
            # Each group: using 'count' strings of length L
            # This is like a 0-1 knapsack item with weight = L*count, value = count
            weight = L * count
            if weight > W:
                continue
            for w in range(W, weight - 1, -1):
                if dp[w - weight] + count < dp[w]:
                    dp[w] = dp[w - weight] + count
    
    if dp[W] == INF:
        print(-1)
    else:
        print(dp[W])

solve()

---

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