FC2ブログ
--.--
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

08.14
Thu
動的計画法が苦手なので典型問題を解いているんだけど、思った事があったのでメモ。

まず現段階で自分はdpテーブルを定義して配列の添字をごちゃごちゃ考えてやるやつがようわからんので、(思いつかなそうなのとバグだらけになりそう)メモ化再帰で全て書いている。(トップダウンで解くのかボトムアップで解くのかの違いらしいので。(ただ再帰だといくらかオーバーヘッドがあったりする場合があるのと、稀にメモ化再帰だとできない問題があるらしい?))

でだ。メモ化再帰で怖いと思ったのはメモしてるつもりになってて実は全然そのメモが使われてなくて(メモの仕方が間違ってて)実質的に全探索になってしまってる事があるなーということ。しかも小さいテストケースだとそれでも通ってしまう。
具体的にやっちまったやつとして複数個の品物を入れれるknapsack問題とか最小枚数で両替するやつとかうまくメモ化できてなかった。対して、01knasackとかはうまくできてた。
メモ化再帰で解いてるコードが比較的少ないっぽい感じなのでdp配列を定義してやってる、解説コードを読むんだけど
前者の問題は1次元配列で後者は多次元(2次元)配列だった。メモ化再帰でいうなら、引数が1つと2つってことになんのかな。
自分は複数個の品物を許すknapsack問題も両替のやつも引数が2つで、メモ用の配列も二次元配列なんだけど、そこの違いなのかな。(うまくメモにヒットしない風になってる?)

スポンサーサイト

comment 0 trackback 0
トラックバックURL
http://telracsmoratori.blog.fc2.com/tb.php/193-91432ca3
トラックバック
コメント
管理者にだけ表示を許可する
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。