DPL_1_C - ナップザック問題

動的計画法について、基本的な問題（ナップザック問題）をPythonで解いてみました！

前回の記事とほとんど同じコードで解くことができます。 dp[i+1][w]の求め方が少し違います。

dp[n][w]は「n番目までの商品を、重さwを超えないで選んだ時の最大値」です。

DPL_1_C - ナップザック問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=ja

~
#入力データの処理
N,W = map(int,input().split())
vwl = []
for _ in range(N):
    v,w = map(int,input().split())
    vwl.append((v,w))

#動的計画法の準備
dp = [[0]*(W+1) for _ in range(N+1)]

#動的計画法の実行
for i in range(N):
    vi,wi = vwl[i]
    for w in range(W+1):
        if w-wi>=0:#dp[i][w-wi]が二次元配列の外に行かないか判定
            #次行変更箇所
            dp[i+1][w] = max(dp[i+1][w-wi]+vi,dp[i][w])#重さwiのものを取るべきか判定
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])
~