今回は、0/1ナップサック問題を動的計画法を使って解いてみましょう。
動的計画法とは、最適化問題をより単純な部分問題に分解し、全体問題の最適解がその部分問題の最適解に依存することを利用して解くアルゴリズム手法です。
0/1ナップサックは、おそらく動的計画法の下で最も人気のある問題です。
また、動的計画法のコツをつかむために学ぶのに最適な問題です。
この記事では、0/1ナップザックとは何か、そしてPythonで動的計画法を用いてどのようにこの問題を解くことができるかを学びます。
それでは始めましょう。
0/1ナップサックの問題文
動的計画法の問題文は次の通りです。
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. |
まず、すべての品目の重さを表す重みの配列がある。
また、すべての項目の値を持つ値配列と、ナップサックの総重量がある。
これらの情報が与えられたとき、重量制限の範囲内で得られる最大値を求める必要がある。
この問題は、ある品物を全体として含めるか、除外するかのどちらかであるため、0/1ナップザックと呼ばれる。
つまり、ある品目の端数を取ることはできない。
理解するために例を挙げてみましょう。
次のような入力値があるとします。
val = [50,100,150,200]
wt = [8,16,32,40]
W = 64
|
ここで、1,2,4の品目を含めると、200 + 50 + 100 = 350となり、利益が最大となる。
したがって、利益の合計は次のようになる。
350 |
動的計画法を使って0/1ナップサックを解くには？
動的計画法を用いて0/1ナップサックを解くには、次のような次元の表を作成します。
[n + 1][W + 1]
|
表の行は0からnまでのアイテムに対応します。
表の列は 0 から W までの重量制限に対応します。
表の最後のセルのインデックスは:
[n][W] |
インデックス[i][j]のセルの値は、0からiまでのアイテムと総重量制限をjと考えたときに可能な最大の利益を表します。
表を埋めた後、私たちの答えは表の一番最後のセルになります。
テーブルを埋めるには？
これは、0番目の行はオブジェクトがないことを意味し、0番目の列は可能な最大の重量が0であることを意味するからです。
ここで、各セル[i][j]に対して、2つのオプションがあります。
-
- オブジェクト[i]を最終的な選択に含めるかどうか。
-
- オブジェクト[i]を最終的な選択項目に含めない。
対象物[i]を選択範囲に入れるかどうかは、どのように決定するのでしょうか？
対象物[i]を含めるためには、二つの条件を満たす必要があります。
- 1.対象物[i]を含めた総重量が、制限重量を超えないこと。
-
- 対象物[i]を含めた場合の利益が、含めない場合よりも大きくなること。
0/1 ナップサックについて理解したことを Python コードに変換してみましょう。
0/1 ナップサックを解く ## Python コード
以下のリスト内包メソッドでテーブルを作成してみましょう。
table = [[0 for x in range(W + 1)] for x in range(n + 1)]
|
ネストされたforループを使って表を走査し、各セルにエントリーを埋めていきます。
テーブルをボトムアップで埋めていく。
for i in range(n + 1):
for j in range(W + 1):
if i == 0 or j == 0:
table[i][j] = 0
elif wt[i-1] <= j:
table[i][j] = max(val[i-1]
+ table[i-1][j-wt[i-1]], table[i-1][j])
else:
table[i][j] = table[i-1][j]
|
コードを一行ずつ分解してみましょう。
if i == 0 or j == 0:
table[i][j] = 0
|
この部分は、0番目の行と列に0を設定する役割を担っています。
elif wt[i-1] <= j:
|
このコードはi番目のオブジェクトの重量がそのセルで許容される総重量(j)よりも小さいことをチェックします。
table[i][j] = max(val[i-1]
+ table[i-1][j-wt[i-1]], table[i-1][j])
|
このコード行は2つの選択肢のうち最大値を選択する役割を担っている。
オブジェクトを含めるか、除外するかのどちらかです。
ここで、table[i – 1][j] という用語は、i番目の項目が含まれないことを意味します。
val[i – 1] + table[i – 1][j – wt[i – 1]]の項は、i番目の項目が含まれることを表している。
else:
table[i][j] = table[i-1][j]
|
このループの部分は、i番目の物体の重量が許容限界(j)より大きいときにアクセスされる。
テーブルを埋め終わったら、テーブルの最後のセルを答えとして返すことができる。
return table[n][W]
|
ナップザック解答関数の完全なコード
ナップサックを解く関数の完全なコードは以下の通りです。
def knapSack(W, wt, val):
n=len(val)
table = [[0 for x in range(W + 1)] for x in range(n + 1)]
for i in range(n + 1):
for j in range(W + 1):
if i == 0 or j == 0:
table[i][j] = 0
elif wt[i-1] <= j:
table[i][j] = max(val[i-1]
+ table[i-1][j-wt[i-1]], table[i-1][j])
else:
table[i][j] = table[i-1][j]
return table[n][W]
|
上の例題に対して関数を実行してみましょう。
val = [50,100,150,200]
wt = [8,16,32,40]
W = 64
print(knapSack(W, wt, val))
|
コンプリートコード
以下は、あなたのシステムで実行するための完全なコードです。
def knapSack(W, wt, val):
n=len(val)
table = [[0 for x in range(W + 1)] for x in range(n + 1)]
for i in range(n + 1):
for j in range(W + 1):
if i == 0 or j == 0:
table[i][j] = 0
elif wt[i-1] <= j:
table[i][j] = max(val[i-1]
+ table[i-1][j-wt[i-1]], table[i-1][j])
else:
table[i][j] = table[i-1][j]
return table[n][W]
val = [50,100,150,200]
wt = [8,16,32,40]
W = 64
print(knapSack(W, wt, val))
|
このコードを実行すると、次のような出力が得られます。
350 |
まとめ
Pythonの動的計画法を使って、0/1ナップサックを解くチュートリアルでした。
楽しく学んでいただけたら幸いです。