DPL_1_B - 0,1ナップザック問題 動的計画法
動的計画法について、基本的な問題(ナップザック問題)をPythonで解いてみました!
dp[n][w]は「n番目までの商品を、重さwを超えないで選んだ時の最大値」です。
DPL_1_B - 0,1ナップザック問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&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][w-wi]+vi,dp[i][w])#重さwiのものを取るべきか判定 else: dp[i+1][w] = dp[i][w] print(dp[N][W]) ~