概要

重量制限 \(S\) 以下かつ純利益の合計が \(T\) 以上となる依頼の選び方が存在するか判定し、存在する場合は選ぶ依頼数の最小値を求める問題です。0/1ナップサック問題の変種として、動的計画法（DP）で解きます。

考察

問題の整理

各依頼 \(i\) には以下の3つの値があります： - 純利益: \(P_i - C_i\)（負になることもある） - 重量: \(W_i\)

ここから、重量の合計が \(S\) 以下かつ純利益の合計が \(T\) 以上となる部分集合のうち、要素数が最小のものを求めたいです。

素朴なアプローチ

全ての部分集合を列挙すると \(2^N\) 通りで、\(N = 50\) のとき \(2^{50} \approx 10^{15}\) となり到底間に合いません。

重要な気づき

「選んだ個数 \(k\) を固定したとき、ちょうど \(k\) 個選んで重量 \(S\) 以下で得られる最大利益はいくらか？」を求められれば、\(k = 0, 1, 2, \ldots\) と小さい方から順に調べて、最大利益が \(T\) 以上になる最初の \(k\) が答えになります。

これは0/1ナップサック問題の拡張で、状態に「選んだ個数」を追加すれば解けます。

アルゴリズム

DP の定義

\(dp[k][w]\) = ちょうど \(k\) 個の依頼を選び、荷物の総重量がちょうど \(w\) であるときの、純利益の合計の最大値

• 初期状態: \(dp[0][0] = 0\)、それ以外は \(-\infty\)
• 遷移: 各依頼 \((profit_i, w_i)\) について、0/1ナップサックと同様に逆順にループ

\[dp[k+1][w + w_i] = \max(dp[k+1][w + w_i],\ dp[k][w] + profit_i)\]

ただし \(w + w_i \leq S\) の場合のみ遷移します。逆順に走査するのは、同じアイテムを2回以上使わないためです。

答えの求め方

全アイテムの処理後、\(k = 0, 1, 2, \ldots, N\) の順に以下を確認します：

\[\max_{0 \leq w \leq S} dp[k][w] \geq T\]

これを最初に満たす \(k\) が答えです。どの \(k\) でも満たさなければ -1 を出力します。

具体例

例えば \(N=3, S=10, T=5\) で依頼が \((profit=3, w=4), (profit=4, w=5), (profit=2, w=3)\) のとき： - \(k=1\): 最大利益は \(4\)（2番目の依頼のみ）→ \(T=5\) に届かない - \(k=2\): \((profit=3+4=7, w=4+5=9 \leq 10)\) → \(7 \geq 5\) なので答えは \(2\)

計算量

• 時間計算量: \(O(N^2 \times S)\)
  • 各アイテム（\(N\) 個）について、\(k\)（最大 \(N\)）と \(w\)（最大 \(S\)）の二重ループを回すため
  • \(N = 50, S = 10000\) のとき約 \(2.5 \times 10^7\) で十分高速
• 空間計算量: \(O(N \times S)\)
  • DP テーブルのサイズ

実装のポイント

• 逆順ループ: 0/1ナップサックでは、同じアイテムを複数回使わないために \(k\) と \(w\) を大きい方から小さい方へ走査します。これを忘れると同じ依頼を何度も選んでしまいます。

• 純利益が負の依頼: \(P_i - C_i < 0\) の依頼も存在し得ますが、DP の遷移で自然に扱えます（選ぶと利益が減るので、最適解では通常選ばれません）。

• 到達不可能な状態の管理: \(dp[k][w] = -\infty\) の状態からは遷移しないようにチェックすることで、実際には到達できない状態を正しく除外します。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    S = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    items = []
    for i in range(N):
        P = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        W = int(input_data[idx]); idx += 1
        profit = P - C
        items.append((profit, W))
    
    # DP: dp[w] = (max_profit, min_count_for_that_max_profit)
    # We want to find minimum count such that weight <= S and profit >= T
    # 
    # Better approach: dp[w] = dict or we do 2D DP
    # Since we want to minimize count, let's do:
    # For each number of items k (from 0 to N), check if it's achievable.
    # But that's complex too.
    #
    # Alternative: dp[w] = maximum profit achievable with weight exactly w, and for each state also track minimum items.
    # But we need to be more careful: among all subsets with weight <= S and profit >= T, minimize count.
    #
    # Let's do: dp[w][count] = max profit with total weight w using exactly count items
    # That's O(N * S * N) which is O(50 * 10000 * 50) = 25,000,000 - feasible.
    #
    # Or: for each count k from 0..N, dp_k[w] = max profit using exactly k items with weight w
    # Return first k where max over w<=S of dp_k[w] >= T
    
    # dp[w] = max profit achievable with weight exactly w, using minimum items
    # Actually let's track: dp[w] = list where dp[w] gives max profit for weight w
    # and we want min count. 
    #
    # Cleaner: dp[w] = (max_profit, min_count) isn't right because max profit with fewer items 
    # might be less than max profit with more items.
    #
    # Best approach: dp[w] = {count: max_profit} but that's expensive.
    #
    # Let me think again. We want minimum count. So iterate k from 0 to N:
    # For each k, check if there's a subset of exactly k items with weight <= S and profit >= T.
    # Use DP: after considering all items, dp[k][w] = max profit using exactly k items with weight exactly w.
    # Answer = smallest k such that max(dp[k][w] for w in 0..S) >= T.
    # Space: O(N * S) = O(50 * 10000) = 500,000. Time: O(N^2 * S) = O(50 * 50 * 10000) = 25M. Fine.
    
    NEG_INF = float('-inf')
    
    # dp[k][w] = max profit using exactly k items with total weight exactly w
    # k ranges 0..N, w ranges 0..S
    # We only care about w <= S
    
    # Initialize: dp[0][0] = 0, everything else = -inf
    # For memory efficiency, use 2D array dp[N+1][S+1]
    
    dp = [[NEG_INF] * (S + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    
    for profit, w in items:
        # Traverse in reverse to avoid using same item twice (0/1 knapsack)
        for k in range(min(N, N) - 1, -1, -1):  # from N-1 down to 0
            for ww in range(S + 1):
                if dp[k][ww] == NEG_INF:
                    continue
                new_w = ww + w
                if new_w <= S:
                    new_profit = dp[k][ww] + profit
                    if new_profit > dp[k + 1][new_w]:
                        dp[k + 1][new_w] = new_profit
    
    for k in range(N + 1):
        max_profit = NEG_INF
        for ww in range(S + 1):
            if dp[k][ww] > max_profit:
                max_profit = dp[k][ww]
        if max_profit >= T:
            print(k)
            return
    
    print(-1)

solve()

---

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