ナップザック問題（Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、動的計画法によるナップザック問題（Knapsack Problem）について学んでいきます。

動的計画法とは
ナップザック問題とは
Pythonでナップザック問題を作成
動作確認
参考書籍

動的計画法とは

前回までに学んだアルゴリズムの中のクイックソートでは、配列全体を分割していきながら、最終的に配列全体をソートするという分割統治法による手法を用いました。

しかし、分割統治法では分割していく過程の中で、すでに解決した問題を再び解いてしまうことによる、負荷の増大が発生する場合があります。

動的計画法（Dynamic Programming）では、分割した小問題をテーブルに記録しておき、分割する過程ですでに解決済みの問題に当たった場合は、テーブルからその結果を引き出す手法をとるため、分割統治法での無駄な手間がかからないメリットがあります。

ナップザック問題とは

ナップザック問題（Knapsack Problem）とは、ある容量のナップザックがあり、その中に $n$ 種類の品物（品物にはそれぞれ容量と価値が決められている）を入れる際に、価値が最大になるにはどの品物をどのように組み合わせて入れるべきかを考えることを言います。

例えば、以下のテーブルに示すような品物があった場合、ナップザックの容量が10とすると価値が最大になるにはどれを詰め込むべきかを考えます。

正解は、品物1と3を詰めた場合で大きさ10、価値合計は15で最大となります。

Pythonでナップザック問題を作成

それでは、Pythonでナップザック問題の解を求めるスクリプトを作成します。

# knapsack.py
import sys

size    = [2, 3, 5, 7, 9]
value   = [2, 4, 7, 11, 14]
N       = len(size)
MAX_N   = 200

if len(sys.argv) != 2:
    print("Usage: {} ")
    sys.exit(1)
knapsack_size = int(sys.argv[1])
print("size of knapsack is {}.".format(knapsack_size))
if knapsack_size >= MAX_N:
    printf("size of knapsack is too big.")
    sys.exit(1)

total   = [0 for _ in range(MAX_N)]
choice  = [-1 for _ in range(MAX_N)]

for i in range(N):
    for j in range(size[i], knapsack_size+1):
        repack_total = total[j-size[i]] + value[i]
        if repack_total > total[j]:
            total[j] = repack_total
            choice[j] = i
    print("i = {}".format(i))
    print("total\t= ", end="")
    for j in range(knapsack_size+1):
        print("{:2d} ".format(total[i]), end="")
    print()
    print("choice\t= ", end="")
    for j in range(knapsack_size+1):
        print("{:2d} ".format(choice[j]), end="")
    print()

i = knapsack_size
while choice[i] >= 0:
    print("put item: {}, value: {} in knapsack.".format(choice[i],
                value[choice[i]]))
    i -= size[choice[i]]
print("total value: {}.".format(total[knapsack_size]))

動作確認

それでは上記で作成したスクリプトを実行してみます。

品物の大きさと価値はfig1のテーブルをそのまま使っています。

 > python knapsack.py 10
 size of knapsack is 10.
 i = 0
 total   =  0  0  0  0  0  0  0  0  0  0  0
 choice  = -1 -1  0  0  0  0  0  0  0  0  0
 i = 1
 total   =  0  0  0  0  0  0  0  0  0  0  0
 choice  = -1 -1  0  1  0  1  1  1  1  1  1
 i = 2
 total   =  2  2  2  2  2  2  2  2  2  2  2
 choice  = -1 -1  0  1  0  2  1  2  2  1  2
 i = 3
 total   =  4  4  4  4  4  4  4  4  4  4  4
 choice  = -1 -1  0  1  0  2  1  3  2  3  3
 i = 4
 total   =  4  4  4  4  4  4  4  4  4  4  4
 choice  = -1 -1  0  1  0  2  1  3  2  4  3
 put item: 3, value: 11 in knapsack.
 put item: 1, value: 4 in knapsack.
 total value: 15

問題なく最大価値を計算できていることが確認できました。