0-1ナップザック問題を思い出す

プログラマになりたいくせにしばらくプログラミングから離れていたらものの見事に忘れ果てていたので、基本に立ち返ることにした。まずはナップザック問題から。

n, maxw = list(map(int, input().split()))
v_lis, w_lis = [], []   # in order, list for values, and for weights

# set data
for _ in range(n):
    v, c = list(map(int, input().split()))
    v_lis.append(v)
    w_lis.append(c)

# 外側が商品番号、内側が最大許容量とする
# (Outer is for index of products, inner is maximum allowable amount)
dp = [[0 for _ in range(maxw+1)] for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, maxw+1):
        if j>=w_lis[i-1]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_lis[i-1]]+v_lis[i-1])
        else:
            dp[i][j] = dp[i-1][j]

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

久しぶりすぎて基本のDPすらすっかり忘れていた。一番役に立ったのがはじめてこの問題を解いていた当時のメモ

手順のおさらい

dp[i, j]: i番目までの品物を入れる・入れないの判断をして重さがj以下になるときの「最大の価値」←最終的に出力したい答えであり、dp[N, W]で表せられる。

dp[N+1, W+1]の配列を確保、dp[0, j], dp[i, 0]は適当な小さい値で初期化

漸化式を解く。 dp[i, j] = Max([入れない場合], [入れた場合])

入れない場合はi番目の品物を無視するのでi-1番目と変わらず、dp[i-1, j]となる

入れる場合はi-1番目の時点でのjからi番目の品物の重さを引き、i番目の品物の価値を足したものになる。dp[i-1, j-i番目の品物の重さ] + i番目の品物の価値

というやつ。ちなみにこのメモに書いてあったんだけど、

2次元配列でやっているが、実際はループの構造からもわかるように、ひとつ上のインデックスを見て現在の重さを判断している。要はひとつ前のリストのみによって現在のリストを更新しているので、実質はひとつのリストしか必要ない。

ということなので、このような最終的に最大化した価値だけを求める典型問題だと最大許容量+1ぶん詰める1次元配列だけあればいい。

n, maxw = list(map(int, input().split()))

dp = [0 for _ in range(maxw+1)]
for i in range(n):
    v, c = list(map(int, input().split()))
    for j in range(maxw, -1, -1):
        if j>=c:
            dp[j] = max(dp[j], dp[j-c]+v)
        else:
            break
print(dp[-1])

AOJでは、最初のやりかただと1000ミリ秒ちょい、短くしたバージョンだと600ミリ秒くらいになった。

電波ビーチ

☆（ゝω・）v

0-1ナップザック問題を思い出す