概要

荷物の重量制限と必要な純利益を満たすように配達依頼を選び、その中で選ぶ依頼の個数が最小となるものを求める問題です。

考察

この問題は「荷物の重量の合計が \(S\) 以下」かつ「純利益の合計が \(T\) 以上」という2つの制約を満たす依頼の選び方の中で、選ぶ個数が最小のものを求める問題です。各依頼は「選ぶ/選ばない」の2択なので、部分和問題の変種と見なせます。

素朴な全探索では \(2^N\) 通り（\(N \leq 50\) なので \(2^{50} \approx 10^{15}\)）の選択肢を調べることになり、計算量が大きすぎて現実的ではありません。そこで、動的計画法を用いて効率的に解くことを考えます。

アルゴリズム

動的計画法で以下のようなDPテーブルを構築します： - dp[count][s]: ちょうど count 個の依頼を選び、荷物の総重量が s であるときの純利益の最大値

DPテーブルの初期化： - dp[0][0] = 0（0個選んだときの純利益は0） - それ以外は十分小さい値（\(-10^9\)）で初期化

各依頼について、現在の状態から「その依頼を選ぶ」場合の遷移を行います。選ぶ個数 count と重量 s について、後ろからループすることで、同じ依頼を重複して選ばないようにします。

全てのDP状態を計算した後、dp[count][s] >= T かつ s <= S を満たす状態の中で、最小の count を求めます。そのような状態が存在しない場合は -1 を出力します。

計算量

• 時間計算量: \(O(N^2 \cdot S)\)
  • 依頼数 \(N\)、選ぶ個数 \(N\)、重量 \(S\) の3重ループ
• 空間計算量: \(O(N \cdot S)\)
  • DPテーブルのサイズが \(N \times S\)

実装のポイント

• DPテーブルは2次元配列で、[選んだ個数][総重量] で管理

• 同じアイテムを重複して選ばないように、ループは後ろから回す

• 初期値は十分小さい負の値に設定（未到達状態を表現）

• 最終的に条件を満たす最小の個数を探す

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    n = int(data[0]); S = int(data[1]); T_req = int(data[2])
    P = []; C = []; W = []
    index = 3
    for i in range(n):
        p = int(data[index]); c = int(data[index+1]); w = int(data[index+2])
        index += 3
        P.append(p)
        C.append(c)
        W.append(w)
        
    profits = [P[i] - C[i] for i in range(n)]
    
    INF = float('inf')
    min_items = INF
    
    dp = [[-10**9] * (S+1) for _ in range(n+1)]
    dp[0][0] = 0
    
    for i in range(n):
        w_i = W[i]
        profit_i = profits[i]
        for count in range(i, -1, -1):
            for s in range(S, -1, -1):
                if dp[count][s] != -10**9:
                    new_s = s + w_i
                    if new_s <= S:
                        new_profit = dp[count][s] + profit_i
                        if new_profit > dp[count+1][new_s]:
                            dp[count+1][new_s] = new_profit
                            
    for count in range(n+1):
        for s in range(S+1):
            if dp[count][s] >= T_req:
                if count < min_items:
                    min_items = count
                    
    if min_items != INF:
        print(min_items)
    else:
        print(-1)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。