FLYING

〈全日本・紀文豆乳飲料シリーズ「麦芽コーヒー」の500ミリリットルパックを扱う小売店が少ないことに遺憾の意を表明する会〉活動記録

Dynamic Programming

ヤバい。ヤバすぎる。あるNP問題を解くプログラムを今まで総当り方式で作ってたんだが、これを動的計画法使って書き直したらとんでもなく早くなった。具体的に言うと、1時間ほっといても答え出てこなかった問題が1秒かからず解ける感じ。3600倍のスピード。有り得ねー。パソコンとかない時代に動的計画法を思いついたRichard Bellmanは超偉い。かなり半端ない。オレは馬鹿だから解法を理解するのに数日かかったけど、これはやる価値あった。すげー。もうナップサック問題とか怖くねー。メモリ食うのが不安っちゃ不安だけどとりあえずそれは脇に置いておけ。あとやらなくちゃいけないレポートに手を付けないでプログラミングしてるオレも結構すげー。