2017年 秋期 応用情報技術者試験 問3

ナップザック問題

【ナップザック問題】

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

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

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

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

品物の容積や価値を正の整数に限定したナップザック問題に対して、動的計画法による解法が知られている。この問題に対する動的計画法は、元の容積制限以下の全ての値を容積制限としたときの、品物の種類を限定した問題（以下、小問題という）をあらかじめ解いておき、それらの解を用いることによって、元の問題の解を得る方法である。表2に示すような、選んだ品物の最大の価値合計を求める表に対して順に数値を埋めて考えると、この解法の手順は理解しやすい。

表2において、例えば、表1に示す品物A、Bを選べる場合の容積制限3までの小問題が解けているとする。この状態で、容積制限が4で品物A、Bを選べる場合の解は、次の考え方で求めることができる。

・容積制限が4で品物Aだけを選べる小問題の解は、表2から8であることが分かる（下線①部分）。

・品物A、Bを選べる場合、品物Bの容積が2であるので、4から2を減じた容積制限2で品物A、Bを選べる小問題の価値合計（下線②部分）に、品物Bの価値6を加えた12の価値合計を得られることが分かる。

・8と12を比較し、大きい方の12を、容積制限4の場合の価値合計として表2に記入する。これは、最後に品物Bを選んだことを意味する。

表2の空白の部分をこの手順に従って順に埋めていくと、容積制限が5のときの価値合計は14であることが分かる。

容積制限4の場合に最後に品物Bを選んだように、各容積制限の小問題を解いたときに最後に選んだ品物を表3に示す。

容積制限5では、最後に品物Bを選んだことが分かる。次に、品物Bの容積を引いた容積制限3では、最後に品物Bを選んでいる。これを続けていくと、価値合計14を実現する品物の組合せは、品物Aが1個、品物Bが2個であることが分かる。

表1の問題に対して、新たに、容積が3で価値が9である品物Cが追加されたときの問題を解くには、表2に品物A、B、Cを選べる場合の行を追加した表4を順に埋めていけばよい。

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

ナップザック問題に対する動的計画法によるプログラムを図1に示す。なお、Vはナップザックの容積制限、Nは品物の種類の数である。種類s（0～N-1）の品物の容積と価値は、それぞれ、size[s]、value[s]に格納されている。また、maxvalue[t]は、容積制限tの小問題の価値合計を保持する配列である。choice[t]は、容積制限tの小問題を解いたときに最後に選んだ品物を保持するための配列である。この配列は、選んだ品物の組合せを最後に出力するために使用する。なお、全ての配列の添字は0から始まる。

// 初期化
for(k を 0 から V まで 1 ずつ増やす)
    maxvalue[k] ← 0
    choice[k] ← -1    // -1 は、品物が選ばれていないことを示す。
endfor

// 動的計画法メイン。N は品物の種類の数、V はナップザックの容積制限。
for(s を 0 から N-1 まで 1 ずつ増やす)
    for(t を size[s]から V まで 1 ずつ増やす)
        temp ← maxvalue[オ] + value[s]
        if(temp が maxvalue[t]より大きい)
            カ ← temp
            choice[t] ← s
        endif
    endfor
endfor

// 結果の出力。選んだ品物と価値合計を出力する。
k ← V
while(choice[k]が 0 以上)
    choice[k]を出力
    k ← k - size[キ]
endwhile
クを出力 // 価値合計を出力する。

【計算量に関する検討】

動的計画法を用いてナップザック問題を解く場合の計算量のオーダは、品物の種類の数をN、ナップザックの容積制限をVとすると、O(ケ)である。