電波ビーチ

☆(ゝω・)v

0-1ナップザック問題をメモ化再帰で思い出す

前回の続きというか書き忘れ

or3.hatenablog.com

DPは配列でやるのがよく入門でみかけるんだけど、最初に学習するときって順序的にはDFSからのメモ化再帰からのDPっていう感じのほうが理に適っている感じがある。なのでメモ化再帰バージョンを。

# 典型的ナップザック問題の典型的メモ化再帰による解法
# solution of typical DP by typical memo recursion for typical knapsack problem
n, maxw = map(int, input().split())

dp = [[0 for _ in range(maxw+1)] for _ in range(n+1)]
v_list, w_list = [], []
for i in range(n):
    _v, _w = map(int, input().split())
    v_list.append(_v)
    w_list.append(_w)

def check(idx, w):
    # 既に探索済み
    # avoid already passed
    if dp[idx][w]>0:
        return dp[idx][w]
    # インデックスの上限値を越えるのでやめておく
    # avoid over maximum index
    if idx==n:
        return 0
    elif w_list[idx]>w:
        # 現在の商品を入れると制限を越える場合は諦めてインデックスを進める
        # next index because current product's weight much more than current allowable amount 
        return check(idx+1,w)
    else:
        # 現在の商品を選択するか否か。
        # choose to much valuable
        dp[idx][w] = max(check(idx+1, w-w_list[idx])+v_list[idx], check(idx+1,w))
        return dp[idx][w]
# 探索をインデックス0, 許容量maxwからスタートする
# start search by index=0, amount=maxw
print(check(0, maxw))