スタートページ> Web教材一覧> オペレーションズリサーチ
ナップザック問題とは、「ナップザックの容量Qと、n個の品物について、体積 wi とナップザックに入れることの利益 fi が与えられたとき、利益を最大にする、入れるべき品物を求めよ」という問題です。
これを定式化すると、
目的関数:f1xi + f2xi + ・・・ + fnxi →最大
制約条件:w1xi + w2xi + ・・・ + wnxi =Q≦Qmax
xi=0または1
となります。
動的計画法による解法
最適性の原理により、品物iまでを対象にして、ナップザックの容量をQとしたときの最大利益 pi(Q) は、次のように定式化されます。
i=1のとき
p1(Q) = 0 0≦Q<w1
= f1 w1≦Q≦Qmax
i=2~nのとき
pi(Q) = pi-1(Q) Q<wi
品物iを入れられないので、以前の品物の構成は変わらない。
= max{ wi≦Q≦Qmax(品物iを入れる余裕があるとき)
pi-1(Q) ・・・A
pi-1(Q-wi) + fi ・・・B
}
Aが大ならば、品物iを入れないので、以前の品物構成は変わらない。
Bが大ならば、品物iを入れる。
容量の余裕は Q-wi になる。
以前の構成は、容量が Q-wi の最適構成になる。
(これが「最適化の原理」の考え方)
数値例
ナップザックの容量:Qmax=8
品物の個数:n=4
体積 利益
品物1 2 3
↓ 品物2 4 7
i 品物3 1 1
品物4 3 8
i=1のとき(品物1だけが対象のとき)
p1(Q) = 0 (0≦Q<2) 品物1が入らないので、利益=0
= 3 (2≦Q≦7) 品物1が入るので、利益=3
容量Q 0 1 2 3 4 5 6 7 8
品物1 0 0 1 1 1 1 1 1 1
体積合計 0 0 2 2 2 2 2 2 2
利益P1 0 0 3 3 3 3 3 3 3
i=2のとき(品物2も対象になったとき)
p2(Q) = p1(Q) Q<4(品物2を入れられないとき)
= max{ p1(Q) , p1(Q-4) + 7 } 4≦Q≦8
Q<4のとき(品物2を入れられないとき)
品物構成(品物1の選択)は変化しない。
i=1をコピーする。
p2(Q) = p1(Q)
容量Q 0 1 2 3
品物1 0 0 1 1
品物2 0 0 0 0
体積合計 0 0 2 2
利益P2 0 0 3 3
Q=4のとき
p2(4) = max{ p1(4) = 3
p1(0) + 7 = 0 + 7 = 7 ←大
}=7
品物2を入れる。容量0の余裕がある。
容量4の品物1に、i=1、Q=0をコピーする。
容量Q 0 1 2 3 4
品物1 0 0 1 1 0
品物2 0 0 0 0 1
体積合計 0 0 2 2 4
利益P2 0 0 3 3 7
Q=5のとき
p2(5) = max{ p1(5) = 3
p1(1) + 7 = 0 + 7 = 7 ←大
}=7
品物2を入れる。容量1の余裕がある。
容量5の品物1に、i=1、Q=1での値をコピーする。
容量Q 0 1 2 3 4 5
品物1 0 0 1 1 0 0
品物2 0 0 0 0 1 1
体積合計 0 0 2 2 4 4
利益P2 0 0 3 3 7 7
Q=6のとき
p2(6) = max{ p1(6) = 3
p1(2) + 7 = 3 + 7 = 10 ←大
}=10
容量Q 0 1 2 3 4 5 6
品物1 0 0 1 1 0 0 1
品物2 0 0 0 0 1 1 1
体積合計 0 0 2 2 4 4 6
利益P2 0 0 3 3 7 7 10
以下同様にして、Q=8のとき
容量Q 0 1 2 3 4 5 6 7 8
品物1 0 0 1 1 0 0 1 1 1
品物2 0 0 0 0 1 1 1 1 1
体積合計 0 0 2 2 4 4 6 6 6
利益P2 0 0 3 3 7 7 10 10 10
i=3のとき(品物3も対象になったとき)
p3(Q) = p2(Q) Q<1(品物2を入れられないとき)
= max{ p1(Q) , p1(Q-1) + 1 } 1≦Q≦8
Q<1のとき(品物1を入れられないとき)
p3(Q) = p2(Q)
容量Q 0
品物1 0
品物2 0
品物3 0
体積合計 0
利益P3 0
Q=1のとき
p3(1) = max{ p2(1) = 0
p2(0) + 1 = 0 + 1 = 1 ←大
}=1
容量Q 0 1
品物1 0 0
品物2 0 0
品物3 0 1
体積合計 0 1
利益P3 0 1
Q=2のとき
p3(2) = max{ p2(2) = 3 ←大
p2(1) + 1 = 0 + 1 = 1
}=3
容量Q 0 1 2
品物1 0 0 1
品物2 0 0 0
品物3 0 1 0
体積合計 0 1 2
利益P3 0 1 3
Q=3のとき
p3(3) = max{ p2(3) = 3
p2(2) + 1 = 3 + 1 = 4 ←大
}=4
容量Q 0 1 2 3
品物1 0 0 1 1
品物2 0 0 0 0
品物3 0 1 0 1
体積合計 0 1 2 3
利益P3 0 1 3 4
Q=4のとき
p3(4) = max{ p2(4) = 7 ←大
p2(3) + 1 = 4 + 1 = 5
}=7
容量Q 0 1 2 3 4
品物1 0 0 1 1 0
品物2 0 0 0 0 1
品物3 0 1 0 1 0
体積合計 0 1 2 3 4
利益P3 0 1 3 4 7
Q=5のとき
p3(5) = max{ p2(5) = 7
p2(4) + 1 = 7 + 1 = 8 ←大
}=8
容量Q 0 1 2 3 4 5
品物1 0 0 1 1 0 0
品物2 0 0 0 0 1 1
品物3 0 1 0 1 0 1
体積合計 0 1 2 3 4 5
利益P3 0 1 3 4 7 8
Q=6のとき
p3(6) = max{ p2(6) = 10 ←大
p2(5) + 1 = 7 + 1 = 8
}=10
容量Q 0 1 2 3 4 5 6
品物1 0 0 1 1 0 0 1
品物2 0 0 0 0 1 1 1
品物3 0 1 0 1 0 1 0
体積合計 0 1 2 3 4 5 6
利益P3 0 1 3 4 7 8 10
Q=7のとき
p3(7) = max{ p2(7) = 10
p2(6) + 1 = 10 + 1 = 11 ←大
}=11
容量Q 0 1 2 3 4 5 6 7
品物1 0 0 1 1 0 0 1 1
品物2 0 0 0 0 1 1 1 1
品物3 0 1 0 1 0 1 0 1
体積合計 0 1 2 3 4 5 6 7
利益P3 0 1 3 4 7 8 10 11
Q=8のとき
p3(8) = max{ p2(8) = 10
p2(7) + 1 = 10 + 1 = 11 ←大
}=11
容量Q 0 1 2 3 4 5 6 7 8
品物1 0 0 1 1 0 0 1 1 1
品物2 0 0 0 0 1 1 1 1 1
品物3 0 1 0 1 0 1 0 1 1
体積合計 0 1 2 3 4 5 6 7 7
利益P3 0 1 3 4 7 8 10 11 11
i=4のとき(品物4も対象になったとき)
p4(Q) = p3(Q) Q<3(品物4を入れられないとき)
= max{ p3(Q) , p1(Q-3) + 8 } 3≦Q≦8
Q<3のとき(品物2を入れられないとき)
p4(Q) = p3(Q)
容量Q 0 1 2
品物1 0 0 1
品物2 0 0 0
品物3 0 1 0
品物4 0 1 0
体積合計 0 1 2
利益P4 0 1 3
Q=3のとき
p4(3) = max{ p3(3) = 4
p3(0) + 8 = 0 + 8 = 8 ←大
}=8
容量Q 0 1 2 3
品物1 0 0 1 0
品物2 0 0 0 0
品物3 0 1 0 0
品物4 0 0 0 1
体積合計 0 1 2 3
利益P4 0 1 3 8
Q=4のとき
p4(4) = max{ p3(4) = 7
p3(1) + 8 = 1 + 8 = 9 ←大
}=9
容量Q 0 1 2 3 4
品物1 0 0 1 0 0
品物2 0 0 0 0 0
品物3 0 1 0 0 1
品物4 0 0 0 1 1
体積合計 0 1 2 3 4
利益P4 0 1 3 8 9
Q=5のとき
p4(5) = max{ p3(5) = 8
p3(2) + 8 = 3 + 8 = 11 ←大
}=11
容量Q 0 1 2 3 4 5
品物1 0 0 1 0 0 1
品物2 0 0 0 0 0 0
品物3 0 1 0 0 1 0
品物4 0 0 0 1 1 1
体積合計 0 1 2 3 4 5
利益P4 0 1 3 8 9 11
Q=6のとき
p4(6) = max{ p3(6) = 10
p3(3) + 8 = 4 + 8 = 12 ←大
}=12
容量Q 0 1 2 3 4 5 6
品物1 0 0 1 0 0 1 1
品物2 0 0 0 0 0 0 0
品物3 0 1 0 0 1 0 1
品物4 0 0 0 1 1 1 1
体積合計 0 1 2 3 4 5 6
利益P4 0 1 3 8 9 11 12
Q=7のとき
p4(7) = max{ p3(7) = 11
p3(4) + 8 = 7 + 8 = 15 ←大
}=15
容量Q 0 1 2 3 4 5 6 7
品物1 0 0 1 0 0 1 1 0
品物2 0 0 0 0 0 0 0 1
品物3 0 1 0 0 1 0 1 0
品物4 0 0 0 1 1 1 1 1
体積合計 0 1 2 3 4 5 6 7
利益P4 0 1 3 8 9 11 12 15
Q=8のとき
p4(8) = max{ p3(8) = 11
p3(5) + 8 = 8 + 8 = 16 ←大
}=16
容量Q 0 1 2 3 4 5 6 7 8
品物1 0 0 1 0 0 1 1 0 0
品物2 0 0 0 0 0 0 0 1 1
品物3 0 1 0 0 1 0 1 0 1
品物4 0 0 0 1 1 1 1 1 1
体積合計 0 1 2 3 4 5 6 7 8
利益P4 0 1 3 8 9 11 12 15 16
これより、最適解は次のようになります。
選択 体積 利益
品物1 0 0 0
品物2 1 4 7
品物3 1 1 1
品物4 1 3 8
合計 8 16
0-1ナップザック問題では、各品物の個数は1個だけでしたが、それを拡張して、同じ品物が複数個あり、「どの品物をいくつ入れればよいか」という問題にします。すなわち、
Xi=0,1,2,・・・
となります。
実務的には、Xi≦Xmaxi の制約が必要になることが多いのですが、複雑になるので省略します。
定式化
i=1のとき
X=0,1,2,・・・について、
Q=w1X~wi(X+1)-1 の間(ただしQ≦Qmax)
Xopt1(Q)=X
P1(Q)=f1X
i=2~nのとき
Q<wi のとき
品物iは入らないので、品物j(<i)の構成は変わらない。
Xoptj(Q)=Xoptj(Q)
Pi(Q)=Pi-1(Q)
Q≧wi のとき
X=1,2,・・・について、
wiX≦Q<wi(X+1)-1 の間(ただしQ≦Qmax)
次のAとBを計算して、大のほうを採用する。
A:品物iを入れないとき、品物j(<i)の構成は変わらない。
Xoptj(Q)=Xoptj(Q)
A=Pi(Q)=Pi-1(Q)
B:品物iを入れるとき、
Xoptj(Q)=X
残りの容量は、Q-wiXなので、
Xoptj(Q)=Xoptj(Q-wiX)
B=fiX+Pi-1(Q-wiX)
数値例
先の0-1ナップザックの数値で、同一品物がたくさんある場合の表を作成してみます。
i=1
容量Q 0 1 2 3 4 5 6 7 8
品物1 0 0 1 1 2 2 3 3 4
利益P1 0 0 3 3 6 6 9 9 12
i=2
容量Q 0 1 2 3 4 5 6 7 8
品物1 0 0 1 1 0 0 1 1 0
品物2 0 0 0 0 1 1 1 1 2
利益P2 0 0 3 3 7 7 10 10 14
i=3
容量Q 0 1 2 3 4 5 6 7 8
品物1 0 0 1 1 0 0 1 1 0
品物2 0 0 0 0 1 1 0 1 2
品物3 0 1 0 1 0 1 1 1 0
利益P3 0 1 3 4 7 8 10 11 14
i=4
容量Q 0 1 2 3 4 5 6 7 8
品物1 0 0 1 0 0 1 0 0 1
品物2 0 0 0 0 0 0 0 0 0
品物3 0 1 0 0 1 0 0 1 0
品物4 0 0 0 1 1 1 2 2 2
利益P4 0 1 3 8 9 11 16 17 19
これより、最適解は次のようになります。
選択 体積 利益
品物1 1 2 3
品物2 0 0 0
品物3 0 0 0
品物4 2 8 16
合計 8 19