概要

各依頼を「重さ \(W_i\)、純利益 \(V_i=P_i-C_i\)」の品物とみなし、総重量 \(S\) 以下で純利益合計 \(T\) 以上を達成できるかを判定し、達成できるなら選ぶ個数を最小化します。

考察

• 条件は「重さ制約付きで利益を一定以上」に加えて「選ぶ個数の最小化」まで求めています。
  単なる 0/1 ナップサック（重さ以内で利益最大）だけでは、何個選んだかを追えないため最小個数が分かりません。
• では「利益 \(T\) 以上を満たす最小個数」を直接 DP しようとしても、
  • 利益の合計は最大で \(50 \times 10^4 = 5\times 10^5\) 程度まで伸び得て、利益軸の DP は重くなりがち
  • さらに \(V_i\) は負にもなり得るため、利益軸 DP は扱いが難しくなります（インデックスが負になるなど）。
• ここで重要なのは、\(N \le 50\) と小さい点です。
  「何個選んだか」は最大でも 50 なので、個数を DP の次元として持つのが有効です。

アルゴリズム

次の DP を考えます。

• \(dp[k][w] =\) 「ちょうど \(k\) 個選んで、総重量が \(w\) のとき達成できる純利益の最大値」
• 初期化：
  • 何も選ばず重さ 0 のとき利益 0：\(dp[0][0]=0\)
  • それ以外は不可能なので \(-\infty\)（コードでは大きな負数 NEG）

各依頼（純利益 \(v\)、重さ \(w\)）について 0/1（高々1回）で選ぶので、遷移は以下です。

• 既に \(dp[k][cw]\) が可能なら、その依頼を追加して
  • 個数：\(k \to k+1\)
  • 重さ：\(cw \to cw+w\)（ただし \(cw+w \le S\)）
  • 利益：\(dp[k][cw] + v\) と更新します。

0/1 ナップサックと同様に、同じ依頼を複数回使わないために - 個数 \(k\) を大きい方から（降順） - 重さ \(cw\) も大きい方から（降順） に回して更新します。

最後に、\(k=1,2,\dots,N\) の小さい順に - \(\max_{0\le w\le S} dp[k][w] \ge T\) を満たす最小の \(k\) を答えとして出力し、存在しなければ -1 です。

計算量

• 時間計算量: \(O(N^2 S)\)
  （各依頼ごとに、\(k=0..N\)、重さ \(0..S\) を回すため。制約下では最大でもおよそ \(50^2 \times 10^4 = 2.5\times 10^7\) 程度）
• 空間計算量: \(O(NS)\)
  （\(dp\) 配列が \((N+1)\times(S+1)\)）

実装のポイント

• 到達不能状態は NEG（十分小さい値）で埋め、NEG のときは遷移しないようにします。

• 0/1 条件を守るため、更新ループは 個数も重さも降順にします（昇順だと同一依頼を同じループ内で複数回使ってしまう危険があります）。

• \(W_i > S\) の荷物は、どのみち積めないのでスキップして構いません。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    S = next(it)
    T = next(it)

    items = []
    for _ in range(N):
        p = next(it)
        c = next(it)
        w = next(it)
        items.append((p - c, w))

    NEG = -10**18
    dp = [[NEG] * (S + 1) for _ in range(N + 1)]
    dp[0][0] = 0

    for v, w in items:
        if w > S:
            continue
        for k in range(N - 1, -1, -1):
            prev = dp[k]
            nxt = dp[k + 1]
            limit = S - w
            for cw in range(limit, -1, -1):
                pv = prev[cw]
                if pv == NEG:
                    continue
                nw = cw + w
                nv = pv + v
                if nv > nxt[nw]:
                    nxt[nw] = nv

    ans = -1
    for k in range(1, N + 1):
        if max(dp[k]) >= T:
            ans = k
            break
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。