前回の続きというか書き忘れ
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))