大きなナップサック【解説】

本稿はCodeIQで2013年12月16日～2014年1月20日に出題された「大きなナップサック」という問題の解法に関する記事です。

問題文はこちら

大きなナップサック【解説】

◆01ナップサック問題

今回解説するのは、ナップサック問題の中でも“単一制約の01ナップサック問題”と呼ばれる種類のものです。ちょっと長いですから、今後は単に“ナップサック問題”と表記します。ナップサックに入れる品物には、値段と重量の2要素があり、重量が“制約”に相当します。また、品物1つひとつについては、ナップサックの中に、入れる／入れないという2つの状態がありますので、これは0と1で表現できることから、“01”と呼ばれています。

大きめのナップサック問題を解く場合に用いられる手法として有名なものは、動的計画法と分枝限定法ですが、どちらも難しそうな名前をしています。まずは、これらの手法の本質的な部分のみを簡単に説明しておきます。

◆動的計画法と分枝限定法

動的計画法や分枝限定法そのものについては、ウェブ上にも書籍にもたくさん解説がありますので、詳細は省略して、必要な部分のみを簡単に説明しておきます。

• 動的計画法のエッセンス

簡単に言うと、「一度計算した結果は保存しておいて、必要になったら使いましょう。ただし、計算途中でもっと良い結果が出たらどんどん置き換えていきますよ」という考え方です。品物一つひとつについて、ナップサックに入れる場合と入れない場合の両方を調べてみて、「同じ重量でもより良い詰め方があれば、きちんと更新する」という操作を繰り返すことで、「一番良い詰め方を積み上げていく」ことになります。

• 分枝限定法のエッセンス

名前から想像がしやすいと思いますが、探索時の枝刈り手法のことです。このまま探索するとして、仮に一番良い解が得られるとすれば、どの程度かということを見積もって（上界値）、現時点で知られている解（下界値）を超える可能性があるかどうかをルールとして枝刈りします。詳細を書くと非常に長くなりますので、この辺りは他の資料を参考にしてください。もし、上界値という言葉に馴染みがなければ、“上界値”や“線形緩和”で検索してみてください。

◆動的計画法と分枝限定法のハイブリッド

ナップサック問題を高速に解くためには、動的計画法と分枝限定法の考え方を、両方取り入れる必要があります。動的計画法では、以前に計算した結果と比べて良いものを記録しておきますが、それが将来的に役立つ（最適解につながる可能性がある）かどうかは全く考慮されていません。そこで、動的計画法をベースに、上界値・下界値を用いて、不必要な状態は取り除いていきます。こうすることで、計算量・消費メモリの大幅削減が期待できます。

アルゴリズム	速度	メモリ消費
動的計画法	速い	ナップサックの容量に比例（つまり今回の問題ではかなり消費する）
分枝限定法	まあまあ	探索方法に依存（深さ優先にすると省メモリ）
ハイブリッド	かなり速い	ナップサックの容量に依存するものの、実際はかなり抑えることができる

◆最適解の特徴を掴む

一般的な動的計画法では、探索順序（どの品物から調べるか）ということはあまり考慮されません。分枝限定法では、どの品物から調べるかによって探索時間が大きく変わるので、探索順序は大切な要素になります。まずは最適解がどのようなイメージなのかを、図を用いて確認しておきます。

◆貪欲解

ナップサック問題で“そこそこの解”を得るには、各品物について値段÷重量（＝価値）を計算し、この値が大きいものから順に選ぶ方法があります。これを貪欲解と呼び、品物を単にソートするだけでそれらしい解が得られるのですから、それほど悪い方法ではありません。

貪欲解を、図で表してみます。左に向かって価値が大きく、右に向かって価値が小さいとし、その品物を選ぶ場合を1、選ばない場合を0とします。

貪欲解では、左から1がならび、右の方はすべて0になります。

この方法では、高速にそれらしい解が得られますが、それが最適解になることは少ないですから、いくらか工夫が必要になります。

◆最適解

実際に最適解を求めると、01の並びは次のようになる場合が多いです。

全体的には、左側に1がたくさんあり、右側に0がたくさんあるので、貪欲解と大きな差はないように見えます。

◆“コア”という考え方

左の方に現れる0は「価値が高いのに要らない」、右の方に現れる1は「価値は低いけど要る」ということで、このような要素をいかに素早く見つけ出すかが、ナップサック問題を解くポイントになります。

左側から見て最初に0が現れるところから、最後に1が現れるところまでを“コア”と呼び、コアが大きいほど探索の工夫が難しくなります。あまりにコアが大きい場合は、シンプルな動的計画法を並列化するなりした方が速い場合もありますが、実際には問題の規模（品物の数）に対してコアはそれほど大きくなりません。

◆アルゴリズム

上記の点を踏まえて、アルゴリズムの概要を考えてみます。

(1)品物を価値の高い順に並べる

(2)価値の高い順にナップサックに詰め込み、その状態（貪欲解）を初期状態とする また、貪欲解の場合の1が続く部分と0が続く部分の境界を、コアの左端・右端とする

(3)左端・右端をひとつ広げる 左端を広げる場合は品物を取り除く操作 右端を広げる場合は品物を加える操作

(4)品物を出し入れした状態について、それぞれ次の3点についてテストを行い、すべてパスした状態をリストに加える 実行可能性…そのまま探索して、制約条件を満たす解が得られるかどうかを調べる 優越性…同じ重量で値段の違う候補があれば、値段の高いものだけを残す 上界値…上界値の計算を行い、下界を上回るものだけを残す

(5)コアを広げて(3)へ戻る ※細かい分岐やデータ構造は省略していますので、ご了承ください。

詳細は、以下のコードをご覧ください。 https://bitbucket.org/ozy4dm/01knapsack/src/886505f885f146cc76c843cf4289c529ad65c5af/codeiq/

◆解の圧縮・復元

単に“値段の合計の最大値”を答えるだけであれば気にする必要はありませんが、“品物を入れる／入れないの情報（01の並び）”まで答えなければならない場合、厄介な問題が起こります。動的計画法の考えを用いた場合、状態の1つひとつに01情報を加えてしまうと、消費メモリが膨大になってしまいます。消費メモリを押さえるための工夫としては、いくつかアイデアがあります。

• ビットベクトル

01だけの情報ですから、たとえば32ビット整数であれば品物32個分の情報を詰め込むことができます。10000個の品物があれば、10000÷32＝312.5で、サイズが313の配列を用意すればすべての01情報を保持することができます。これくらいのサイズであれば、状態数が10000個あったとして、12MB程度で済みます。

• 貪欲解との差分

前述したように、最適解と貪欲解で01が異なる箇所はそれほど多くありません。そこで、貪欲解と異なる箇所のindexのみを保持するようにします。よほど意地悪く作られたテストケースでなければ、これだけでも十分省メモリになります。

• コアの情報

コアの情報、つまり“最初に0が現れるところと最後に1が現れるところのみを保持するだけにしておいて、ほとんどメモリを消費せず解いてしまいます。次に、コアの部分に該当する品物だけを抽出し、再度解きます。これを繰り返し、問題の（コアの）規模が十分小さくなったところで、先に挙げたビットベクトルや貪欲解との差分を利用した解き方に切り替えます。

• 01データの圧縮（はにゃわさん案）

挑戦者のはにゃわさんによるアイデアです。非常に効果的だと思いましたので、ここで紹介しておきます。

10000個もあるデータの01情報ですが、最適解が貪欲解に近いということは、価値の高い順に並べて置いた場合、0や1が大量に続く可能性が高いと考えられます。そこで、0と1の連続数のみを記録することで、01情報をかなり小さくすることができます。通常のランレングス圧縮は、簡単に言えば「どの文字が」「いくつ続くか」という情報で記録していく方法ですが、01のみという条件であれば、「どの文字が」という部分を省略することができます。必ず0から始まると仮定しておけば、たとえば10個品物があるとして、

0000000000 -> { 10 } (0が10個)
1111111111 -> { 0 } (0が0個, 残りは全部1)
0001111100 -> { 3, 5 } (0が3個, 1が5個, 残りは全部0)
1111001111 -> { 0, 4, 2 } (0が0個, 1が4個, 0が2個, 残りは全部0)

のような感じで記録することができます。

◆前処理

簡単な問題ではあまり必要ありませんが、難しい問題になるといくらか前処理を行っておくと、さらに効率よく解くことができます。

• より良い下界値を

探索に入る前、特に工夫をしない場合は貪欲解を下界値に設定します。この部分をもう少し工夫して、複数（2～3個）の品物の01状態を固定した上で貪欲法を用いるとか、仮想のコアを適当に決めてその範囲のみで問題を解くということをすると、より良い下界値が見つかる場合があります。

• 探索前のカット

探索前に良い下界が見つかっていると、事前にいくつかの品物の状態を決められる場合があります。具体的には、各品物について、「その品物を“入れた場合の”上界値A」と、「“入れない場合の”上界値B」を計算します。このとき、

B ≦ (下界値) < A

であれば、その品物は必ず入れなければ最適解を得ることができないとわかります。

A ≦ (下界値) < B

であれば、その品物を入れてしまうと最適解が得られないことがわかります。

これにより、問題の規模を小さくすることができる場合があります。ほとんど効果がない場合もありますが、計算量が増えるように作為的に作られた問題に対しては絶大な効果を発揮することもあります。

◆その他の工夫

細かい工夫は他にもできると思いますので、いろいろ研究してみてください。実装の仕方によってもかなり速度差が出ます。紹介したソースコードをコンパイル・実行すると、まずまずの高速に厳密解が得られますが、可変長の配列を使っていたり、配列のコピーを頻繁に行っていますので、固定長の配列にするとか、コピーの回数を最小限に抑えるためにポインタを駆使したりすると、かなり高速に仕上げることができます。

「とにかく高速化！」とか、「どこまで大規模な問題が解けるか」など、目標を設定して取り組めば、まだまだ面白いアイデアが出てくるかもしれません。