ナップサック問題

ナップサック問題とは

ナップサック問題は、ナップサックに入れる荷物の組み合わせを考える問題です。 それぞれの荷物には重さと価値が設定されており、ナップサックの容量制限を超えずに最も価値のある組み合わせを見つける問題です。 （ちなみに特定の荷物を複数回選ぶことはできないこととします。この制約がある場合を特に「0-1ナップサック問題」と呼びます）

単純な問題に思えますが「組み合わせ」という言葉が示す通り、荷物の数が増えれば増えるほどに選択肢が爆発に増加し、全てのパターンを試すのが非常に困難になります。 そのため、効率的に最適解を見つけるアルゴリズムが求められます。

これは最適化問題の一例であり、動的計画法などを用いて解決されることが一般的です。

全ての組み合わせを試す

問題を見て最初に思い付くのが単純に全ての組み合わせを試す方法でしょう。ひとまず、配列を再帰的に組み合わせていく方法を考えてみます。

入力の一行目がナップサックの容量制限と荷物の数、続く行が各荷物の価値と重さを表す形式とします。

サンプルコードでは容量制限5のナップサックに対して、三種類の荷物を考えます。荷物はそれぞれ（価値: 6, 重さ: 2）、（価値: 10, 重さ: 3）、（価値: 12, 重さ: 4）です。

ビット演算を用いて全ての組み合わせを列挙する方法もあります。再帰的な方法よりもコードがシンプルになる場合があります。

どちらも正しい解法です。しかし、荷物の数を増やしてみるとステップ数が一気に増えます。全ての組み合わせを試すというのが実用的ではないことは直感的にわかるでしょう。

動的計画法を用いた解法

ナップサック問題を効率的に解くために、動的計画法を用いましょう。

基本的な考え方は小さな部分問題の解を組み合わせて大きな問題の解を導くことです。ナップサック問題では、縦軸に荷物、横軸に容量の表を作成し、各セルにその時点での最大価値を記録していきます。

具体的には左上から右下へ各マスを埋めていきます。各マスについて、その荷物を入れない場合と入れる場合の価値を比較し、より大きい方を採用します。入れない場合は１つ上のマスの値をコピー、入れる場合はその荷物の価値＋残りの容量に対応する左側のマスの値を足したものになります。

例えば荷物2の容量4のマスを埋める時は、入れない場合は上のマスの値6、入れる場合は荷物2の価値10＋残りの容量1のマスの値0で合計10となり、より大きい10の値を採用します。

次の荷物2の容量5のマスを埋める時は、入れない場合は上のマスの値6、入れる場合は荷物2の価値10＋残りの容量2のマスの値6で合計16となり、より大きい16の値を採用します。

こうすれば表の各マスにその時点での最大価値が記録され、最終的に右下のセルに最大価値が得られます。この方法なら全ての組み合わせを試す必要が無く、計算量は表の各マスを埋めるO(荷物の数×容量)で済みますね。

以下にTypeScriptでの実装例を示します。

上のマスと左のマスを参照するという、一度計算した部分問題の解を再利用を行っています。こうすることで、全ての組み合わせを試す方法に比べて大幅に効率化できることがわかります。

上記の解法の問題

ところで、上記の動的計画法による解法には問題点があることに気付きましたか？

１つ目は、メモリ使用量が大きくなる可能性があることです。特に荷物の数や容量が大きくなると、DP表のサイズも大きくなり、メモリを大量に消費することになります。

２つ目は、容量や重さが整数でなければならないことです。でなければ事前に表を作れません。

画期的な解法に思えましたが万能ではありません。ナップサック問題には他にも様々な解法が提案されており、問題の特性に応じて適切なアルゴリズムを選択することが重要です。

まとめ

ナップサック問題は組み合わせ最適化問題の一例であり、全ての組み合わせを試す方法では計算量が爆発的に増加するため、動的計画法などの効率的なアルゴリズムが求められます。

TypeScriptでの実装例を通じて、ナップサック問題の基本的な解法とその限界について理解できたかと思います。実際の問題に取り組む際には、問題の特性に応じて最適なアルゴリズムを選択し、効率的な解決策を見つけることが重要です。

今回の実装例を参考に、ナップサック問題に挑戦してみてください。最適な解法を見つけるために、様々なアプローチを試すことが重要です。