• このエントリーをはてなブックマークに追加

今日は、ナップザック問題を勉強しました.

今回は、AOJの問題をPythonで解いてみます.

ナップザック問題については、以下のサイトを参考にしました.

以下、記号の意味などは、上記サイトを参照願いします.

スポンサードリンク

深さ優先探索

N, W = map(int, raw_input().split())

v = [0] * N
w = [0] * N

for i in range(N):
v[i], w[i] = map(int, raw_input().split())

def rec(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]) return res print(rec(0, W)) [/sourcecode]

これだと、時間制限に引っかかって、テストが通らない

メモ化再帰

深さ優先探索を改良.

メモ化のためのテーブル dp を宣言する.

rec(i,j)の結果は、(i,j)によって一意に決まるため、計算結果の dp[i][j]を返す.

N, W = map(int, raw_input().split())

v = [0] * N
w = [0] * N
dp = [[-1 for i in range(W + 1)] for j in range(N + 1)]

for i in range(N):
v[i], w[i] = map(int, raw_input().split())

def rec(i, j):
if dp[i][j] != -1:
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 res print(rec(0, W)) [/sourcecode]

動的計画法

漸化式を解く.

N, W = map(int, raw_input().split())

v = [0] * N
w = [0] * N
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

for i in range(N):
v[i], w[i] = map(int, raw_input().split())

for i in range(N – 1, -1, -1):
for j in range(W + 1):
if j < w[i]: dp[i][j] = dp[i + 1][j] else: dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]) print(dp[0][W]) [/sourcecode]