動的計画法とナップサック問題を学びたい人におすすめのサイト
組み合わせ最適化の手法として「動的計画法」というモノがあります。
動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）
コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法
一見難しそうですが、実は理解するのは以外と簡単です。いろいろな場面で応用が利く便利な手法ですので、覚えておいて損はないものです。コンピュータ系、情報系のお勉強をする人であれば、おそらく一度は習ったりするかもしれません。
ナップサック問題と動的計画法
動的計画法の一番親しみやすそうな例として「ナップサック問題」というのがよく取り上げられます。
こんな感じの問題です。
今ここに様々な大きさの品物が置いてあるとします。そしてそれらの品物は各々値札が着いているとしましょう。
そしてあなたはナップサック（リュックサックでもいい）を１つもっています。
このナップサックに、もっとも合計額が高くなるように、目一杯ぎゅうぎゅうに品物を詰めてください。
イメージしやすいですね。要するに特定の制約条件のもとで利益を最大化させるような話です。実生活でも色々なシーンで遭遇しそうな問題ですね。
さて、このナップサック問題を解こうとすれば、単純に考えれば、すべての品物について「選ぶ／選ばない」の２つの場合を考えて行けばいいので、品物がN個だとすると2のN乗のパターンを総ざらいすれば最適解は求まりそうです。
ところが総当たり方式だと、品物が３０個になっただけで実に1073741824、つまり10億以上のパターンを演算しなければなりません。
このように総当たりでは現実的な時間内で計算できないような問題を数学的には「NP困難」と呼びます。
そこで動的計画法を使ってスマートに最適解を導き出そう、というのがナップサック問題といわれるネタになります。
動的計画法の詳しい説明は解説サイトが数多くあるので、ここでの言及は控えます。
ここではperlを使ってちょっとした例題を解いてみます。
準備
動的計画法はとてもシンプルなアルゴリズムなので、自前で書いてしまっても数十行程度に収まりますが、やはり面倒なので、まずはCPANを探してみます。
あっさりとAlgorithm::KnapとAlgorithm::Knap01DPというモジュールを発見。
今回はKnap01DPを使ってみます。これは0-1ナップサック問題を解くためのモジュールっぽいです。
（商品を１回しか選べない場合は0-1ナップサック問題、複数回選択可能な場合は123ナップサック問題と呼ばれています）
さてさてコード書いてみるか、、、、ん？なんだこれ？？
書き始めてみて気がついたのですが、このモジュール、えらく使いづらいです。。
データをわざわざ別ファイルに持たなければ行けないし、メソッドもなんだか素直じゃない。ちょっと大きめのデータ（数万件程度）を処理したらあっさりout of memoryしてしまうし。実用的なモジュールとは言いがたい印象です。
なので、あくまで「雰囲気を知る」程度に触ってみます。
例題
お題は「遠足で３００円以内で持って行きたいお菓子をえらぶ」というシチュエーションにしましょう。
gooランキングで「遠足のおやつ300円」に必ず入れたいお菓子ランキングという丁度良いネタがあったので、これらのお菓子を候補とします。
# ポッキー 168円 496kcal
# うまい棒 10円 45kcal
# じゃがりこ 145円 325kcal
# ベビースターラーメン 60円 347kcal
# チロルチョコ 10円 61kcal
# かっぱえびせん 124円 486kcal
# サッポロポテト 124円 446kcak
# 都こんぶ 105円 22kcal
# ヨーグレッとは入れもん 126円 110kcal
# おにぎりせんべい 184円 475kcal
（値段とカロリーは適当に調べたのであまり正確ではないです）
さて、これらのお菓子を３００円を上限としてもっとも満足度の高い組み合わせで選びたいと思います。
ちょっと不自然ですが満足度としてカロリーを使います。
肥満児の気持ちになって「３００円以内でカロリーを最大化したい！」と考えて下さい。（どんな子どもだ？）
まずは上記のお菓子の情報を以下のような入力ファイルにまとめます。
okashi.txt
10 # 品物の数
300 # 上限金額
168 # ポッキーの値段
496 # ポッキーのカロリー
10 # うまい棒の値段
45 # うまい棒のカロリー
145 # じゃがりこの値段
325 # じゃがりこのカロリー
60 # ベビースターラーメンの値段
347 # ベビースターラーメンのカロリー
10 # チロルチョコの値段
61 # チロルチョコのカロリー
124 # かっぱえびせんの値段
486 # かっぱえびせんのカロリー
124 # サッポロポテトの値段
446 # サッポロポテトのカロリー
105 # 都こんぶの値段
22 # 都こんぶのカロリー
126 # ヨーグレット／ハイレモンの値段
110 # ヨーグレット／ハイレモンのカロリー
184 # おにぎりせんべいの値段
475 # おにぎりせんべいのカロリー
コードです。
knapsack_test.pl
use strict; use warnings; use Algorithm::Knap01DP; my $file = $ARGV[0]; my $knap = Algorithm::Knap01DP->ReadKnap($file); $knap->solutions(); $knap->ShowResults();
そうすると以下のような結果が得られます。
[miki@godzilla knapsack] $ perl knapsack_test.pl okashi.txt
Problem: okashi.txt
Number of Objects = 10 Capacity = 300
1 (10) 4 (10) 5 (124) 6 (124) Used Capacity = 268
Profit = 1038
これによると１と４と５と６を選ぶと価格が２６８円、満足度が1038で最大だよ、ということになります。
つまり、こうなります！
うまい棒 10円 45kcal
チロルチョコ 10円 61kcal
かっぱえびせん 124円 486kcal
サッポロポテト 124円 446kcal
うーん、そうきたかぁ。。。
うまい棒とチロルチョコの小物２つをおさえつつも、高カロリー・フライ系をしっかりメインに据えてくるあたり、とても合理性を感じます。
まとめ
うまい棒、チロルチョコ、かっぱえびせん、サッポロポテト。。。
大物と小物の組み合わせで４種類のアイテムを展開しつつ1038kcalの堂々の布陣！それでもって268円というリーズナブルな組み合わせ！
「遠足と言えば都こんぶだよね」なんてしたり顔しているあなた
「ポッキーははずせないよね」なんてアタリマエなこと言ってるあなた
だからキミは甘いって言うんです
そんなこと言ってるようでは、さぞかし遠足で惨めな思いをしてきたはず。
大人になった今もきっと幸薄い人生でしょう。
かく言う私もチロルチョコなどの小物には目もくれない強欲な子どもでした。
今すぐ少年時代に戻って「動的計画法」を駆使してお菓子選びから人生をやり直したい今日この頃であります。
まとめなおし
だいぶ脱線したので、まとめなおします。
動的計画法は応用範囲も広いし、エンジニアにとって覚えておくとよい知識だよ、ということで、最後にいくつか参考になりそうなサイトを列挙しておきます。
http://www-or.amp.i.kyoto-u.ac.jp/open-campus-04.pdf
簡単そうで難しい組合せ最適化
京都大学のオープンキャンパスの資料？らしいですが、とてもわかりやすいです。初心者はここから学ぶのがおすすめ。
http://algorithms.blog55.fc2.com/blog-category-6.html
ALGORITHM NOTE 動的計画法
様々な例があってすばらしくわかりやすい。Cによるサンプルコードも勉強になります。
pythonで例示しながら解説してくれています。欲張り法（greedy）についても学べます。
nitoyonさんによるスライド。超大作（165ページもある！）
