スタートページWeb教材一覧オペレーションズリサーチ

動的計画法によるナップザック問題


0-1ナップザック問題

ナップザック問題とは、「ナップザックの容量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)=f1
 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


計算プログラム

ナップザックの容量Qmax=   品物の数n=
i→品物1品物2品物3品物4品物5品物6品物7品物8品物9品物10
体積w→
利益f→
最大個数→
(最大個数は、実行3のときだけ必要。制約がないときnull)