[Algorithm] BaekJoon : 12865. 普通のリュックサックby Python

[問題のショートカット]https://www.acmicpc.net/problem/12865

📌問題の説明

この問題は普通のリュックサックについての問題です.
一ヶ月後に国から召喚されたジュンヒは旅行に行く.悲しい世との隔絶、最大限楽しむ旅なので、持ち歩くリュックもできるだけ安くなります.
旅行が必要だと思っているものがN点ある.どれも重量Wと価値Vがあり、リュックサックに入れると準本でVを楽しむことができます.まだ行軍したことのない俊書は最大Kのリュックサックしか持っていない.できるだけ楽しく旅行するために、リュックサックに入れられるものの価値の最低価格を教えてあげます.
入力
第1行は、物品の数N(1≦N≦100)および準書に耐えられる重量K(1≦K≦100000)を与える.2行目から、N行を経て、各物品の重量W(1≦W≦100000)およびその物品の価値V(0≦V≦1000)が与えられる.
入力した数字はすべて整数です.
しゅつりょく
リュックサックに入れられるアイテムの価値の最高値を1行印刷します.

💡 問題を解く

再帰的な完全ナビゲーション・アクセスを使用しても、問題はタイムアウトしません.(最大100件のアイテムなのでタイムアウト)
したがって、DPを用いてタイムアウト問題を解決することができる.
これはProgrammersの「おつり」と同じ問題です.
→DPテーブルの設定とアクセス(全く同じ)…(そのため、説明は省略)
コードは次のとおりです.

N, K = map(int, input().split())

cases = []
for _ in range(N):
    w, v = map(int, input().split())
    cases.append((w, v))

DP = [[0] * (K+1) for _ in range(N+1)]

for row in range(1, N+1):
    for col in range(1, K+1):
        if col >= cases[row-1][0]:
            DP[row][col] = max(DP[row-1][col], DP[row-1][col-cases[row-1][0]] + cases[row-1][1])
        else:
            DP[row][col] = DP[row-1][col]

print(max(DP[-1]))

反省の一言

前に解決した問題と全く同じですが、考えずに「回帰+完全探索」しただけで時間を無駄にしました.反省:)