ナップサック問題

ナップサック問題
クマさん人形をめぐる熱いドラマの結
末
二人組の泥棒がクマの人形をナップサックの
最大容量が7kgという条件の下で価値が最
大になるように盗もうとしている
• 小さい方から2、3、4、5kg
• 同じく16、19、23、28万円
1.まず1kgあたりの価値を計算し、それの大
きい順にナップサックに入れる
• しかし、この方法ではクマの人形を分割
しないと価値を最大化することができな
い
• この計算方法を貪欲アルゴリズムという
2.次に問題を小さく分割して解く方
法を思いつく
持っていく
or
持っていかない
で2通りに分ける
持っていく
完全列挙法
持っていかない
3.分枝限定法を用いて解くことを思いつく

分枝限定法・・・基本的には完全列挙法
違う点は緩和問題を用いて上界を得ることによって枝き
りをすること
貪欲アルゴリズムで出した値は最適値よりも大きくならない
このことを下界という

緩和問題・・・問題の条件を緩めて最適値
よりも大きい値を出す
これによって得られる値を上界という
・最適値は下界と上界でサンドイッチされて
いる
最大化問題の場合
上界(緩和)
最適値
下界(実行可能) となる
上界と下界が一致していれば、それが最適
値である保証が得られる
• 実際に上界を得るには?さらにこの場合
の緩和問題とは?
最も簡単な方法は整数条件を外して線形
計画緩和問題を考える
 極小クマさん1体
小クマさん1体
中クマさん半分
合計46.5万円
これが上界
46.5万円>貪欲アルゴリズムで出した値35万円
これが下界
上界と下界が一致していないので、これが最適解である保証はない
ここでtreeを使う
上界
46.5万円
上界
42万円
分枝限定法による最適解の探索
上界(19+23=42万円)が
下界(44万円)より小さいので
右半分を調べる必要なし
44万円(下界)
兄貴はシャバに出たら工場から100体のクマさんを盗むと
言い出した
しかし100体になると分枝限定法が有効になるかどうかわ
からない
 制限条件が整数である場合には動的計画
法が有効ということに気づく

動的計画法・・・基本的には最適性の原理を用い
て、小さな部分問題から解いていく方法
実際にさっきの問題で動的計画法を用いてみると
動的計画法の計算図
0
1
2
3
4
5
6
7
なし
0
0
0
0
0
0
0
0
極小
0
0
16
16
16
16
16
16
極小、小
0
0
16
19
19
35
35
35
極小、小、
中
0
0
16
19
23
35
39
42
極小、小、
中、大
0
0
16
19
23
35
39
44
動的計画法の手順
• 手順1.対象物(クマさん)が1つもない場
合から始める。ナップサックの容量によら
ず、持っている価値の合計がすべて0であ
る自明な場合からスタートする
• 手順2.順に対象物の個数を増やしていき
ナップサックの容量別の価値の合計を計
算する
ナップサック問題

n個のアイテムから成る有限集合N、おのおのの
アイテムi
Nの重量 Si と価値 Vi 、およびナッ
プサックの重量の上限bが与えられたとき、アイ
テムの重量の合計がbを超えないようなアイテム
の詰め合わせの中で、価値の合計が最大のもの
を求めよ

ナップサック問題の定式化

アイテムi(N)をナップサックに詰めるとき1、それ以
外の時0になる0-1変数を使うと

x
v
s

iN
最大化
条件
 vi xi
iN si xi  b
iN
i
i
i
i
0,1
x 0,1   N
i
i
ある制約を満たす整数の組で線形関数を最大化(最小
化)するものを見つける問題を、整数計画問題と呼ぶ

貪欲アルゴリズムはきわめて簡単で、単位重量あた
りの価値 vi / i の大きいものから順にbを超えない
限りつめていくだけ
この解法では最適解を得られる保証はないが、問題
の制約を満たした解を常に生成する
これによって得られた解の値は、最適値より小さいか、
等しいことが保証されているので下界と呼ばれる
s




分枝限定法を得るためには、下界の他に常に最適値
より大きいか、等しい値である上界が必要になる
上界は変数 xi の整数条件を緩和した次の問題をとく
ことによって得られる
上界を求めるには

最大化
条件
 vx
 s x b
0  x 1  N
iN
iN
i
i
i
i
i
i
ある制約を満たす実数の組で線形関数を最大化(も
しくは最小化するものを見つける問題を線形計画問
題と呼ぶ
ナップサック問題を線形計画問題に緩和したものは
貪欲アルゴリズムと同じようにして簡単に求まる
単位重量あたりの価値の大きいものから順にbを超
えない限り詰めていく
緩和問題の場合には端数も許す
動的計画法part1

ある物がk種類しかなく、かつナップサックの重量の
上限が  しかないような部分問題を考え、そのとき
の最大値を f k,  とする
f k,  =最大化 ik1 vi xi
条件 i1 si xi  
,
k
xi 0,1 i  1・・・
部分関係間の関係より、 f k,  は次の再帰方
程式によって計算可能である
k
動的計画法part2
f k,   f k 1, 
max f k 1, , vi  f k 1,  si 
f 1,   0
v
1
0    sk
s 
,
  2・・・
k
k
0    s1
s   b
1
n
動的計画法まとめ




再帰方程式を境界条件のもとで順次解いて
いくことによってナップサック問題の最適解を
O(nb)時間で求めることができる
多項式オーダーに見えるが実は違う
擬似多項式空間アルゴリズムである
ナップサック問題はNP困難ではあるが適切
に設定された分枝限定法を用いることによっ
て実用規模の問題も高速に解くことができる