discrete optimization

久々にとってみた。完走できる自身はない。この講座は ちょっと特殊で、最初の一つ意外はどの順番でやってもいいことになっている。 課題もビデオも既に全て公開されていてどの順番でやってもいいらしい。 課題はかなり難しいと予告されているので最近の仕事の状況からするときつそう。

教授はインディアナ・ジョーンズみたいな格好で出てきたりしてかなりキテる。面白い。

1回目はナップザック。とりあえず、DPで解くのを書いてみたけど大きい問題は 全然とけない。大きいのはfirst fit decreasing でお茶を濁したら あんまり点数が良くない。とりあえずまあ、いいか。 DPは関数メモ化部分を工夫して、データを流用するようにするともうすこし 行けるんだろうか。