動的計画法とナップサック問題について解説します。
ナップサック問題は、価値と重さが決まっている複数の品物を容量が一定のナップサックに詰め込むとき、ナップサックに詰め込める品物の価値の和の最大値は何であるか？ という問題です。
具体的には、以下の図のようになります。ナップサックに書かれている「15kg」が容量で、周囲の品物（箱）に書かれている数字が価値と重さを表しています。
画像はWikipediaより改変（Dake, Keenan Pepper / CC BY-SA 2.5）
ナップサック問題についておおざっぱに方針を考えると、以下のような解法が思い浮かぶかもしれません。
全パターンを試せば、明らかに正しい答えを得ることができます。ただし、品物の数をnとすると計算量が$$[O(2^n)]$$ほどあり、まともに計算できるのはnが25くらいまでのときのみです。
優先順位をつける方法なら、品物をソートして容量をオーバーしないようにしながら順に選んでいけるので、高速に計算することができます。
しかし実は、優先順位をつける方法ではどうやっても正しい解を得ることはできません。 上の図の例でいつくかの優先順位を使って最大値を求めたときに得られる解は、次のようになります。
