Pythonで解くナップサック問題【動的計画法（DP）入門】
この記事では競技プログラミング等で頻出のアルゴリズムである「動的計画法」をナップサック問題を通して解説していきます。
まず動的計画法についての解説をしてから、実際にナップサック問題をPythonで解いていきます。
そもそも動的計画法（DP）とは
動的計画法を簡単に説明すると「問題を分割して計算結果を記録しながら解いていく手法」です。
細かく定義されているアルゴリズムではないので一言で動的計画法といっても種類がいくつかあります。
代表的な種類としては以下のようなものがあります。
- ナップサックDP
- 区間DP
- bitDP
今回はこの中のナップサックDPを解いていきますが、難しい！と感じたらより簡単な動的計画法の問題を以下の記事で解説しているので参照してみてください。
nashidos.hatenablog.com
ナップサック問題を解こう
問題文
N 個の荷物があり、i(1≦i≦N) 番目の荷物には価値
と重さ
が割り当てられている。
許容重量 Wのナップサックが1つある。重さの和が W以下となるように荷物の集合を選びナップサックに詰め込むとき、価値の和の最大値を求めよ。ただし、同じ荷物は一度しか選ぶことができない。
制約
入力はすべて整数
1≤N≤100
1≤W≤105
1≤≤W
1≤ ≤109
実装
問題文を読むと「価値」/「重さ」とかで順位付けをして解きたくなりますが今回はそれでは解くことができません。
そこで、動的計画法を利用して「価値」と「重さ」を記録していきます。
実際にやることは2つくらいしかありません。
- DPテーブルを作る
- 条件に応じてテーブルを更新
条件も選ぶOR選ばないの2通りなので難しいことはありません。
選ばない時、すなわち許容重量を超えてしまっているときは
選ぶ時、すなわち許容重量以内であるときは
以下がPythonのサンプルコードです。
N,W = map(int,input().split()) w = [] v = [] for i in range(N): x,y = map(int,input().split()) w.append(x) v.append(y) dp = [[0]*(W+1) for j in range(N+1)] # DPテーブルの作成 for i in range(N): for j in range(W+1): if j < w[i]: # 選ばない時 dp[i+1][j] = dp[i][j] else: # 選ぶ時 dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]) print(dp[N][W])
実際にDPテーブルがどのように更新されていくかを観察してみるとわかりやすいと思います。
# 入力 3 8 3 30 4 50 5 60
# DPテーブルの更新の遷移 [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 30] [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 30] [0, 0, 0, 30, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 30] [0, 0, 0, 30, 50, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 30] [0, 0, 0, 30, 50, 50, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 30] [0, 0, 0, 30, 50, 50, 50, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 30] [0, 0, 0, 30, 50, 50, 50, 80, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 30] [0, 0, 0, 30, 50, 50, 50, 80, 80] [0, 0, 0, 0, 0, 0, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 30] [0, 0, 0, 30, 50, 50, 50, 80, 80] [0, 0, 0, 30, 0, 0, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 30] [0, 0, 0, 30, 50, 50, 50, 80, 80] [0, 0, 0, 30, 50, 0, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 30] [0, 0, 0, 30, 50, 50, 50, 80, 80] [0, 0, 0, 30, 50, 60, 0, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 30] [0, 0, 0, 30, 50, 50, 50, 80, 80] [0, 0, 0, 30, 50, 60, 60, 0, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 30] [0, 0, 0, 30, 50, 50, 50, 80, 80] [0, 0, 0, 30, 50, 60, 60, 80, 0] --------------------------- [0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 30] [0, 0, 0, 30, 50, 50, 50, 80, 80] [0, 0, 0, 30, 50, 60, 60, 80, 90]
