概要

この問題は、所持金 \(M\) 円以内で購入できる屋台の食べ物の組み合わせを選び、満足度の合計を最大化するナップサック問題です。

考察

屋台の数 \(N\) が最大15と小さいため、全探索（\(2^{15} = 32768\) 通り）でも解くことができます。しかし、所持金 \(M\) が最大 \(10^4\) と比較的大きいため、動的計画法（DP）を用いることで効率的に解くことができます。ナップサック問題の典型的なアプローチであるDPを用いることで、各金額における最大満足度を計算し、最終的に最大値を求めることができます。

アルゴリズム

動的計画法を用いて、dp[j] を「金額 j 円以内で得られる最大満足度」と定義します。各屋台の食べ物について、金額 j がその食べ物の値段 T_i 以上の場合、dp[j] を「現在の dp[j]」と「dp[j - T_i] + P_i」の大きい方で更新します。この更新を後ろから行うことで、同じ食べ物を複数回選ぶことを防ぎます。最終的に、dp[0] から dp[M] までの最大値が求める答えとなります。

計算量

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

実装のポイント

• DP配列のサイズは \(M+1\) とし、初期値を0とします。

• 各屋台について、金額 j を \(M\) から \(T_i\) まで減少させながら更新することで、同じ食べ物を重複して選ぶことを防ぎます。

• 最終的に dp 配列の最大値を出力します。

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    M = int(data[1])
    T = []
    P = []
    index = 2
    for i in range(n):
        T.append(int(data[index]))
        P.append(int(data[index+1]))
        index += 2
        
    dp = [0] * (M + 1)
    
    for i in range(n):
        t = T[i]
        p = P[i]
        for j in range(M, t - 1, -1):
            if dp[j] < dp[j - t] + p:
                dp[j] = dp[j - t] + p
                
    print(max(dp))

if __name__ == "__main__":
    main()

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