を参照していく。
7. 問題を解くための技術
ナップサック問題を3通りの方法で解いてみる。
7.2 動的計画法
ナップサック問題を効率的に解く手段の1つとして動的計画法を用いた方法を紹介する。
7.2.1 ナップサック問題への適用
グラフの最短距離の場合と同様に、ナップサック問題でも問題の一部分のみを見て最適化することを考える。例として、
品物 |
重さ |
値段 |
|
---|---|---|---|
品物0 | |||
品物1 | |||
品物2 |
という3つの品物を容量のナップサックに詰める問題を検討する。
そのため以下のように行がどの品物までを考慮したか、列がその時点のナップサック容量を表す表を考える。各セルにはそのときの価値を格納する。
容量0 |
容量1 |
容量2 |
容量3 |
||
---|---|---|---|---|---|
空 | |||||
品物0 | |||||
品物1 | |||||
品物2 |
まず品物0について、容量以外は品物0を格納するから、価値が増す。
容量0 |
容量1 |
容量2 |
容量3 |
||
---|---|---|---|---|---|
空 | |||||
品物0 | |||||
品物1 | |||||
品物2 |
次に品物1の行について、該当する列には1行1列分だけ左上のセルの値に品物1の価値を加算した結果を格納する。
容量0 |
容量1 |
容量2 |
容量3 |
||
---|---|---|---|---|---|
空 | |||||
品物0 | |||||
品物1 | |||||
品物2 |
そして品物2の行について、該当する列には1行2列*1分だけ左上のセルの値に品物2の価値を加算した結果を格納する。
容量0 |
容量1 |
容量2 |
容量3 |
||
---|---|---|---|---|---|
空 | |||||
品物0 | |||||
品物1 | |||||
品物2 |
この表では価値の推移しか分からず、どの品物を入れたかは別で勘定する必要があるが、これにより最適な値を得られる。
7.2.2 動的計画法の実装例
######################################## ### 動的計画法によるナップサック問題 ### ######################################## ### 各種クラスを定義 class Knapsack: def __init__(self, size): # このナップサックが保持できる最大の重さ self.size = size # 現在の重さ self.weight = 0 # 入っている品物の価値の総和 self.value = 0 # 保持するItemの配列 self.items = [] def append(self, item): """ このナップサックにItemを追加する """ if not self.has_room_for(item): raise ValueError('この品物は入れられません。重量オーバーです。') self.items.append(item) self.weight += item.weight self.value += item.price def has_room_for(self, item): """ 引数に取った品物を入れる余裕があるかを真偽値で返す """ return self.size >= self.weight + item.weight def __str__(self): val = '重さ {} kg / 価値 {} 万円'.format(self.weight, self.value) return val ### 動的計画法によるナップサック問題 def dp(items, size_limit): n = len(items) # 価値を記録する表を定義 table = [[0] * (size_limit + 1) for i in range(n + 1)] # 価値を更新したかどうかを記録する表 flg = [[False] * (size_limit + 1) for i in range(n + 1)] # 表を下に進めていくループ for i in range(1, n + 1): # 検討中の品物 target = items[i - 1] w = target.weight # 表を右に進むループ for j in range(1, size_limit+1): # 1行上の最適解 yellow = table[i-1][j] table[i][j] = yellow # 現在の許容範囲jを超えるならば次のループへ if w > j: continue # ちょうどtarget分の重さが少ないときの最適解 pink = table[i-1][j-w] # この品物を入れた場合の価値 include_this = target.price + pink table[i][j] = max(yellow, include_this) flg[i][j] = include_this > yellow # 後処理:表を右下から遡って入れた品物を調べる i = n j = size_limit my_knapsack = Knapsack(size_limit) while i > 0 and j > 0: if flg[i][j]: # この価値更新で追加したのは i-1 my_knapsack.append(items[i-1]) # 表を左へ戻る j -= items[i-1].weight i -= 1 return my_knapsack ### 品物リストを乱数で作成する from collections import namedtuple import random random.seed(7)# 乱数シード # クラスを作成: Item = namedtuple('Item', ('name', 'weight', 'price')) # 品物の個数 num = 20 # 品物を保持するリスト item_list = [] max_weight = 5 # 重さの上限値:乱数で発生させるため # 品物の個数よりも大きな数値にする max_price = 50 # 値段の候補リストを作り、シャッフルする price_list = list(range(1, max_price + 1)) random.shuffle(price_list) # 無作為に品物を作る。名前は番号 for i in range(num): w = random.randint(1, max_weight) item = Item(i, w, price_list.pop()) item_list.append(item) knap_dp = dp(item_list, 40) print(item_list) print(knap_dp)
7.2.3 計算時間
動的計画法の計算時間を見積もる。品物の数をナップサックの容量をとするとき、計算の主要部分はの表を更新する計算である。したがって大雑把にはと擬多項時間で計算できる。
*1:増える重量分の列数だけ左から取る。