駆け出し出遅れプログラミング初心者の日記

こんにちみ(誤植ではない)。鳥居です。

今日は自分なりに動的計画法について、どんな感じで計算していくのかをまとめてみたいと思います。

とはいっても永遠のプログラミング初心者の自分にとっては難しいテーマなので、だいぶ文章がとっ散らかるとは思いますがご了承ください(+_+)

さて、競プロ界隈では知らない人はいないであろう「ナップザック問題」を例にとって考えてみたいと思います。

ご存じナップザック問題とは、「Ｎ個の荷物(それぞれ価値がv,重さがｗグラムである)を最大でWグラム詰めるナップサックに入れていったときの価値の最大値を求める」問題となっています。

ここで、「重さを全く考慮せず無制限にナップザックに入れることができる」としたときの価値の総和はいくつになるでしょう？答えはもちろん、(もし価値が０や負の荷物がなかった場合には)すべての荷物を入れたときの値となります。

次に「重さWまでで価値を無視して荷物を詰め込むときの個数」問題があったとします。この場合の最適解も簡単で、「重さがＷ以下になる最大の荷物の個数(そのまんまだ)」となります。

では、この二つが組み合わさると…？どうすればいいのでしょう？

具体的には「すべての荷物について入れるか入れないかを全探索」する方法が挙げられます。しかしながらこの方法だと計算量が2^Ｎとなり、Ｎが少し大きくなっただけで計算量が一気に増えてしまいます。

じゃあどうすれば…(._.)

ここで登場するのが動的計画法です！

動的計画法について簡単に説明すると、「すでに求まっている一部分の解を利用して次々に最適解を求めていき、最後に問われているクエリの最適解を出す(良い言い方が思いつかないorz)」プログラミング手法です。

ナップザック問題を動的計画法で求める場合だと、

・まず、自明(当たり前)の解を求める(例えば０こ入れたときの解は０…ほんとに当たり前だ）

・次に、その解に重さwを足したときやｎ個の荷物を入れたときの最適解を順々に求めていく。(ここら辺説明するとめんどくさそう…だけど、二次元配列を先に用意しておいて、それぞれの配列に個数と重さを割り当てていって…うーんやっぱりうまく説明できないというか自分の頭の中で整理がつかない…)

・そして最後に、求められている解を出す！

こんな感じですかね？…本当に自分の理解力や説明力のなさが情けない…。

とはいえこう言ったプログラミング手法を知っていると、より効率的なコードが書けるようになると思うので、これからもどんどん吸収していきたいと思います。(最後むりやりまとめた)