3種類の書き方でナップサック問題を解く（Python）

最近「ひぐらしのなく頃に」にハマってます。にぱ～～

無料で視聴させてくれるABEMAには足を向けて寝れません。

ko_ya346です。

今回は動的計画法（DP）の書き方をまとめてみました。

というのも一言にDPと言えど様々な解法（表現？）があるみたいで、

参考サイト毎に書き方が変わっており理解が捗りませんでした。

Atcoderや蟻本を探した結果、とりあえず3種類ほど見つかったのでご紹介します。

問題はこちら。

atcoder.jp

二次元配列

N, W = map(int, input().split())
obj = [list(map(int, input().split())) for _ in range(N)]

dp = [[0 for _ in range(10**5+5)] for _ in range(N+1)]

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

多くの参考サイトで紹介されている書き方です。

アイテム1つに対して配列を一つ持ち、各重みに対して価値を最大化します。

一次元配列

N, W = map(int, input().split())
obj = [list(map(int, input().split())) for _ in range(N)]

dp = [0 for _ in range(10**5+5)]

for i in range(N):
    for j in range(W, obj[i][0]-1, -1):
        dp[j] = max(dp[j], dp[j-obj[i][0]]+obj[i][1])

print(dp[W])

直感的に分かりやすい書き方になっています。

2つめのfor文では先ほどと異なりWから1ずつ減らしていますが、こっちの方が若干行数が減らせます。

Numpy

import numpy as np

N, W = map(int, input().split())
dp = np.zeros((N, W+1), dtype='int64')

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

    #買わない選択肢を引き継ぐ
    dp[i, :w] = dp[i-1, :w]
    dp[i, w:] = np.fmax(dp[i-1, w:], dp[i-1,:W-w+1]+v)
    print(dp)

print(dp[N-1][W])

二次元配列の表現に近いですが、各重みの価値を一括で更新できるためスッキリと書くことができます。

終わりに

まだ完全に理解しているとは言い難いですが、類題をたくさん解いて理解したいと思います。