概要

装備品から防御力の合計が \(K\) 以上となるように選び、攻撃力の合計を最大化する問題です。

考察

各装備品は「選ぶ/選ばない」の2択なので、全ての組み合わせを調べると \(2^N\) 通りとなり、\(N\) が最大100の場合は計算量が膨大になります。そこで動的計画法（DP）を用いて効率的に解くことを考えます。

防御力の合計を状態として、その状態での攻撃力の最大値を保持するDPテーブルを構築します。ただし、防御力の合計の最大値は高々 \(10^6\) 程度（\(N \leq 100\)、\(W_i \leq 10^4\)）なので、DPテーブルのサイズは十分扱える範囲です。

アルゴリズム

1. 初期化: 防御力の合計が \(j\) のときの攻撃力の最大値を格納する配列 dp を用意します。初期値は dp[0] = 0（何も選んでいない状態）とし、それ以外は未達成を表す -1 で初期化します。
2. DPテーブルの更新: 各装備品について、現在の防御力合計 \(j\) から、その装備品を加えた新しい状態 \(j + w_i\) を更新します。このとき、攻撃力の合計がより大きくなる場合のみ更新します（ナップサック問題の要領）。
3. 答えの抽出: 防御力の合計が \(K\) 以上となる全ての状態について、攻撃力の最大値を求めます。該当する状態が存在しない場合は -1 を出力します。

計算量

• 時間計算量: \(O(N \cdot \sum W_i)\)
• 空間計算量: \(O(\sum W_i)\)

実装のポイント

• 装備品を1つずつ処理する際、DPテーブルを後ろから更新することで、同じ装備品を重複して選ぶことを防ぎます。

• 防御力の合計の最大値は全ての装備品の防御力を足した値なので、事前に計算しておきます。

• 必要な防御力 \(K\) が全装備の防御力の合計より大きい場合は、最初に -1 を出力して終了します。

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    K = int(data[1])
    W = []
    S = []
    index = 2
    for i in range(n):
        w = int(data[index])
        s = int(data[index+1])
        index += 2
        W.append(w)
        S.append(s)
    
    max_w = max(W) if n > 0 else 0
    max_total_w = sum(W)
    if K > max_total_w:
        print(-1)
        return
        
    dp = [-1] * (max_total_w + 1)
    dp[0] = 0
    for i in range(n):
        w = W[i]
        s = S[i]
        for j in range(max_total_w, w - 1, -1):
            if dp[j - w] != -1:
                if dp[j] < dp[j - w] + s:
                    dp[j] = dp[j - w] + s
                    
    ans = -1
    for j in range(K, max_total_w + 1):
        if dp[j] > ans:
            ans = dp[j]
            
    print(ans if ans != -1 else -1)

if __name__ == "__main__":
    main()

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