「ナップザック問題」という言葉を聞いたことがありますか？ ナップザックの容量が決まっていて、できるだけ多くの重量を入れたいとか、優先度の高いものをできるだけパックしたい場合の解法です。 データサイエンスの「動的計画法」と呼ばれる解析手法の一つです。
資料をご覧ください → ﾅｯﾌﾟｻﾞｯｸ問題
p.1 「ナップザックの容量は１０Ｌです。できるだけ多くの物品をザックに詰め込むには、どの用品の組み合わせにすればよいか？」という問題です。容量10Lという制約条件があります。A～Eの物品の容量と重量を表にしてあります。下表は横軸が重量、縦軸は空→A→・・・→Eのように一つ一つ物品を入れていきます。セル内の上段の数字は容量、下段はザックに入れた物品のアルファベットを示しています。 （０、空）のセル内は０、物品Aをザックに入れた場合が、赤矢印の先にある赤枠のセルになります。（１、A)のセルで３Aと書いてあります。重量１kg、容量3LのAが入っていると言う意味です。このセルより右のセルは全て同じ３Aです。物品Aしか入っていないからです。 次は、ここに物品Bを入れますので、赤矢印の先の赤枠（４，B)になります。AとB合わせて重量４kg、容量5Lなので、５ABと書かれています。このセルの左側は上の行からコピーし、右側は全て５ABです。 物品Cを入れる場合は、少し複雑になります。 空のザックに物品Cだけを入れると２kgになり４Cとなります。この右隣りは、物品Aを入れて７ACが続き、（６，C)のセルでは、物品Bを入れて）９ABCとなります。赤枠以外の赤線の先は、組み合わせが変わったセルです。 この操作を続けていくと、物品の合計容量が10Lになるのは、重量7kg、容量10Lの物品ACEが入る場合と、重量9kg、容量10Lの物品CDの２通りです。解答は３品種が入る黄色のセル10ACEとなります。
p.2 問題を少し変えて「ナップザックの重量は9ｋｇまで。できるだけ多くの物品をザックに詰め込むには、どの用品の組み合わせにすればよいか？」としました。容量の代わりに、物品の価値を点数化しました。入れる価値が高いほど点数を高くしておきます。今回は、重量が制約条件になっています。 p.1と同様の解答になります。
いかがでしたか？ 我々が頭で考えるとやや面倒臭いですが、このアルゴリズムをAIに入れて計算させれば、あっという間に回答を出してくれると思います。 これからは、データサイエンスの時代です。プログラミングまで知らなくとも、アルゴリズムの種類ぐらいは覚えていきましょう。