ポケットモンスターDP

ポケットモンスターダイナミックプログラミング

ごめんね、お兄さんポケモンの話はしないからごめんね動的計画法の話するからごめんね

ポケモン緑ではいろんなバグを使ってロム1つで全部のポケモン集めました

さて、プログラミングをする上では重要な問題解決法。その1つが動的計画法。

動的計画法とは、問題をいくつかの部分問題に分割して解くというアイデアに加えて、解をもとめた部分問題については解を記録し、同じ部分問題がでたときにその記録しておいた解を再利用する事により、再計算の時間を節約する手法である。

くちでゆーのはちょーかんたん

こういう抽象的な方法を現実問題に対応できるか否かは、その人の技量によります

もちろん僕はその技量があまり無い方ですがorz

今日はpartition problemの問題をやっていたのですが、まぁ、わかるようで、わからないというorz

partition problemはNP困難クラスに属するはずなので、計算量はすぐに青天井

例えば、

1 2 5 9 3 4

という数列において、並び方は変えないで

1 2 | 5 9 | 3 4

のように3つのグループに分けたときに、各グループの和が近くなるようにしなさいという感じ。

上のだと3と14と7ですが

1 2 5 | 9 | 3 4

とすると8、9、7で近くなったねーってなります（多分コレが最適解）

まぁ、ソースには出来なかったんだけど

なんかもう、自分の能力にがっかりする。