コータス先生の動的計画法講座 part1
ナップサック問題とは、それぞれ価値と重さが与えられた荷物と最大容量(入る最大の重さ)の決まったナップサックがあり、そのナップサックにどの荷物を入れれば価値を最大にできるかという問題(正確な問題文は「ナップサック問題」でググろう)。
今回はナップサック問題を数学的に考えてみます。次回はもう少しプログラミング的内容で書きます。
(クチートちゃん)「コータス先生、こんにちは！今日は動的計画法について学びました！」
(コータス先生)「こんにちは、クチートくん。それで、動的計画法についてはわかったのかい？」
「はい、ナップサック問題をやったんですが、漸化式がで与えられることがわかりました！」
「ほう、わかったというのはちゃんと導くことができたということかな？」
「うっ…そう言われると…」
「ほら、いつも何か新しい式を学んだときはしっかりと導き出せるようにしとけって言ってるだろう？」
「そうですね、これじゃただの暗記問題ですもんね。」
「それじゃあナップサック問題について考えてみようか。まずはmax関数を定義しよう。」
「あの、何書いてあるのか全然わからないんですが。」
「まあ、要するに有限な自然数の集合から最大のものを取って来るっていうだけだよ。」
「はぁ…なるほど。」
「そして、このmax関数を使ってナップサック問題の式をそのまま書くと以下のようになるよ。」
「この式もわかんないです…」
「この式はわかった方がいいね、ここから漸化式にもっていく必要があるからね。」
「max関数はさっき定義した集合の最大値を見つける関数ですよね？中の集合は…v(1)からv(N)は価値で、それにxたちをかけて足してる？このxたちはなんですか？」
「xは後ろの条件を見てもらえばわかると思うけど、{0, 1}の集合から取って来てるだろう？つまりオンオフを考えるためのものだよ。0なら入れない、1なら入れる。」
「あ、なるほど、ナップサックに入れるかどうかを決めるためのものだったんですね。それなら後ろの重さについての条件も理解できます。」
「よし、じゃあここから漸化式を作って行こうか。と言っても最適性の原理さえ知っていればそんなに難しくないんだけどね。」
「最適性の原理？なんですかそれ？」
「最適性の原理は『最適解の部分解は，元の問題の部分問題の最適解である』というものだよ。証明もできるけど、まあ常識的に考えても部分解が最適解じゃなかったら元の解も最適解じゃないよね。」
「なるほど。これがどう使えるんでしょう？」
「さっきの式に対して最適性の原理を考えると、任意のk≦Nとy≦Wに対してf(k,y)が部分問題の最適解になることがわかるよ。」
「おお、なるほど！じゃああとはf(k-1,y)からf(k,y)を導けばいいので…でしょうか？」
「おいおい、焦りすぎだよ。それじゃあいくらでも入れられるじゃないか。それにクチートくんが最初に言った公式とも合ってないよ。」
「あ、そうですね。重さも考慮にいれなくちゃいけないし、常に価値が足されるわけではないですよね…。そのためのxですね。k番目のxが0のパターンはf(k-1,y)と変化がないのでそのまま、xが1のパターンは価値が足されるんですがそのために容量を確保しなくちゃいけないのでその分の重さw(k)を引けばいいんでf(k-1,y-w(k))+v(k)ですね！あとはどうやってxを決めるかですね…。」
「それも今回話をしたよ。問題をよく考えて、今回やったことを思い出して見て。」
「えっと、問題は最適解を見つけること。つまり価値をより大きくすること。ということはxが0か1かはそのときの価値が大きい方を取ればいいから…max関数です！」
「それだ！じゃあ早速書いて見て！」
「つまり漸化式はですね！」
「そうだね、ちなみにk=1のときはyとw(1)の大きさを比べてyの方が小さければ0、大きければv(1)を入れてあげればいいよ。」
「そうですね。漸化式なので初期値も用意しなくちゃですよね。」
「これでクチートくんが最初に言っていた漸化式を求めることができたね。」
「難しいですけど、面白いですね。最適性の原理は他にも応用が利きそうです。」
「お、いい目をしているね。キーワードは動的計画法や多段階決定過程だから調べてみるといいよ。」
「はい、精進します！」
「それじゃあ今日はここまでにしようか。」
「ありがとうございましたー！」
まとめ
ナップサック問題の漸化式は以下で与えられる。
