【Matlab / Octave】ナップザック問題

平成29年度 秋期 応用情報技術者試験 午後問題 問3 に出題された「ナップザック問題」のプログラムを Matlab / Octave で作成する。

問題文

ナップザック問題

幾つかの種類の品物があり，それぞれの容積と価値が与えられているとき，選んだ品物の容積の合計が定められた値以下であるという条件（容量制限）を満たし，かつ，価値の合計（以下，価値合計という）が最大になるような品物の組合せを求める問題をナップザック問題（Knapsack Problem）という。

この問題では，一つの品物を選ぶ個数には制限がないものとする。

例えば，容積，価値を表 1 に示した 2 種類の品物 A，B があり，容量制限が 5 である問題を考える。この場合，品物 A を 1 個，品物 B を 2 個選ぶと，容積の合計は 5，価値の合計は 14 となり，選んだ品物の価値合計が最大となる。

	品物 A	品物 B
容積	1	2
価値	2	6

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

品物の容積や価値を正の整数に限定したナップザック問題に対して，動的計画法（Dynamic Programming）による解法が知られている。この問題に対する動的計画法は，元の容量制限以下の全ての値を容量制限としたときの，品物の種類を限定した問題（以下，小問題という）をあらかじめ解いておき，それらの解を用いることによって，元の問題の解を得る方法である。

ナップザック問題に対する動的計画法のプログラム

Matlab / Octave で作成したナップザック問題に対する動的計画法のプログラムを示す。

V=5;# ナップサックの容量制限
N=3;# 品物の種類の数
size=[1,2,3];# 種類 s の容積
value=[2,6,9];# 種類 s の価値

# 初期化
# 容量制限 t の小問題の価値合計を保持する配列
maxvalue=zeros(1,V+1);
# 容量制限 t の小問題を解いたときに最後に選んだ品物を保持するための配列（-1 は，品物が選ばれていないことを示す。）
choice(1,1:V+1)=-1;

# 動的計画法メイン。
for s=1:N
  for t=size(s):V
    temp=maxvalue(t-size(s)+1)+value(s);
    if temp > maxvalue(t+1)
      maxvalue(t+1)=temp;
      choice(t)=s;
    endif
  endfor
endfor

# 結果の出力
# 選んだ品物
choice(1:V)

# 価値合計を出力する
maxvalue(V+1)

上記のプログラムを実行したとき，選んだ品物，価値の合計は，以下のように出力される。

ans =

   1   2   3   2   3

ans = 15

参考文献

• 目指せ！応用情報技術者，「午後問題対策 プログラミング」