概要

この問題は、与えられた \(N\) 個の依頼（アイテム）の中から、「重量の合計が \(S\) 以下」かつ「純利益の合計が \(T\) 以上」という条件を満たすように選び、その時の「選んだ個数の最小値」を求める問題です。

典型的なナップサック問題の応用として、動的計画法（DP）を用いて解くことができます。

考察

まず、各依頼の純利益を \(V_i = P_i - C_i\) と計算します。 私たちが達成したいのは、以下の2点です： 1. \(\sum W_i \leq S\) （重量制限） 2. \(\sum V_i \geq T\) （利益目標） この条件を満たす選び方のうち、選んだ個数 \(k\) を最小化したいという状況です。

なぜ単純なナップサックではないのか？

通常のナップサック問題は「重さの制限内で価値を最大化する」ものですが、今回は「個数を最小化しつつ、価値（利益）の目標も達成する」必要があります。 そのため、DPの「状態」に選んだ個数の情報を持たせる必要があります。

効率的な状態設計

次のようなDPテーブルを考えます。 dp[k][w] ： \(k\) 個の依頼を選び、重量の合計がちょうど \(w\) であるときの純利益の最大値

このように定義すると、すべてのアイテムを処理した後に、dp[k][w] >= T となる最小の \(k\) を探せば答えが得られます。

また、純利益 \(V_i\) が \(0\) 以下の依頼は、選んでも個数 \(k\) が増えるだけで利益は増えない（または減る）ため、最小個数を求める上では考慮する必要がありません。

アルゴリズム

動的計画法（DP）を用いて解きます。

1. 事前準備:
   • 各依頼について純利益 \(V_i = P_i - C_i\) を計算し、\(V_i > 0\) のものだけを抽出します。
2. DPテーブルの定義:
   • dp[k][w] : \(k\) 個選んで重量合計が \(w\) の時の最大純利益。
   • 初期値はすべて -1（到達不能）、dp[0][0] = 0 とします。
3. 遷移: 各依頼 \((V_i, W_i)\) について、現在のDPテーブルを更新します。
   • すでに \(k\) 個で重量 \(w\) に到達できている（dp[k][w] != -1）なら、その依頼を追加して \(k+1\) 個、重量 \(w + W_i\) の状態を作れます。
   • dp[k+1][w + W_i] = max(現在の値, dp[k][w] + V_i)
4. 答えの判定:
   • \(k = 1, 2, \dots, N\) の順に確認します。
   • いずれかの重量 \(w \in [0, S]\) において dp[k][w] >= T であれば、その \(k\) が最小個数です。
   • 最後まで見つからなければ -1 を出力します。

計算量

• 時間計算量: \(O(N^2 S)\)
  • 依頼の数 \(N\)、選ぶ個数の最大 \(N\)、積載量 \(S\) に対して、三重ループ（またはそれに準ずる処理）が発生します。
  • 制約は \(N=50, S=10^4\) なので、\(50 \times 50 \times 10^4 = 2.5 \times 10^7\) 程度の計算量となり、制限時間内に十分収まります。
• 空間計算量: \(O(N S)\)
  • dp[N+1][S+1] のテーブルを保持するためです。

実装のポイント

• 個数の更新順序: 1つの依頼を重複して選ばないよう、個数 \(k\) のループは大きい方から回すか、更新用の別テーブルを用意する必要があります。

• 高速化（到達可能リスト）: Pythonなどの言語では、すべての \(w\) を走査すると重くなる場合があります。コード内では reachable_weights というリストを使い、実際に到達可能な重量のみを更新対象にすることで高速化を図っています。

• 純利益が正のもののみ対象: \(P_i - C_i \leq 0\) の依頼は、目標利益 \(T \geq 1\) を達成するために個数を増やすメリットがないため、除外して考えることができます。

  ソースコード

import sys

def solve():
    # Read all input data at once for speed
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Parse N, S, T from the first three elements
    N = int(input_data[0])
    S = int(input_data[1])
    T = int(input_data[2])
    
    # Parse each request's reward, cost, and weight
    items = []
    for i in range(3, 3 + 3 * N, 3):
        p = int(input_data[i])
        c = int(input_data[i+1])
        w = int(input_data[i+2])
        # Only consider requests with positive net profit
        # Requests with net profit <= 0 will never decrease the minimum count of items
        if p - c > 0:
            items.append((p - c, w))
    
    # If no items have positive profit, and T >= 1, no solution exists
    if not items:
        print("-1")
        return

    # dp[k][w] stores the maximum profit using exactly k items and exactly weight w
    # Initialize with -1 to indicate that the weight is not yet reachable
    dp = [[-1] * (S + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    
    # reachable_weights[k] stores a list of unique weights reachable with exactly k items
    reachable_weights = [[] for _ in range(N + 1)]
    reachable_weights[0].append(0)
    
    # num_items_processed tracks how many requests we've considered so far
    num_items_processed = 0
    for v, w_i in items:
        # Iterate backwards through the number of items to ensure each request is used at most once
        for k in range(num_items_processed, -1, -1):
            dk = dp[k]
            dk1 = dp[k+1]
            rw = reachable_weights[k]
            rw1 = reachable_weights[k+1]
            for w in rw:
                nw = w + w_i
                # Check if the total weight is within the capacity S
                if nw <= S:
                    nv = dk[w] + v
                    # If this weight hasn't been reached with k+1 items yet
                    if dk1[nw] == -1:
                        dk1[nw] = nv
                        rw1.append(nw)
                    # If it has been reached, update it if the new profit is higher
                    elif nv > dk1[nw]:
                        dk1[nw] = nv
        
        # Increment the count of processed items, capped at N
        if num_items_processed < N:
            num_items_processed += 1

    # Find the minimum k such that there exists a weight w with profit at least T
    for k in range(1, N + 1):
        dk = dp[k]
        for w in reachable_weights[k]:
            if dk[w] >= T:
                print(k)
                return
    
    # If no such k is found, print -1
    print("-1")

if __name__ == "__main__":
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。