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

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

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

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

深さ優先探索

[sourcecode language="python" title="" ] 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]を返す.

[sourcecode language="python" title="" ] 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]

動的計画法

漸化式を解く.

[sourcecode language="python" title="" ] 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]