ここでは、ナップサック問題について、 「プログラミングコンテストチャレンジブック(第2版)」(通称:蟻本)の p53 を例に、python3 で実装する方法を紹介します。
時間計算量は、O(nW) です。
# 入力
n = 4
w = [2, 1, 3, 2]
v = [3, 2, 4, 2]
W = 5
#メモ化テーブル(-1 で初期化)
dp = [ [-1 for i in range(W+1)] for j in range(n+1)]
# i番目以降の品物から重さの総和が j 以下となるように選ぶ
def rec(i, j):
if dp[i][j] >= 0:
#すでに調べたことがあるならばその結果を再利用
return dp[i][j]
if i == n:
#もう品物は残っていない
res = 0
elif j < w[i]:
#この品物は入らない
res = rec(i+1, j)
else:
#入れない場合と入れる場合を両方試す
res = max(rec(i+1, j), rec(i+1, j-w[i]) + v[i])
dp[i][j] = res
return dp[i][j]
if __name__ == '__main__':
print(rec(0, W))