ThreeStones https://blog.hatena.ne.jp/ThreeStones/ ThreeStonesのアレ https://threestones.hateblo.jp/ 読書 問題概要 重さwと価値vがついた品物がn個ある。 これらの品物から、重さの総和がWを超えないように選んだときの 価値の総和の最大値を求めなさい。 問題解法 1.全探索 再帰的に、品物をチェックし入れた場合、入れなかった場合とで探索を繰り返す。 重さの総和が超えたり、すべての品物を探索し終えた場合に再帰終了とする。 ▶︎指数時間かかってしまう。2.メモ化 再帰的に呼び出す際、何度も同じ引数による関数呼び出しが発生する。 一度探索している状態については、あらかじめ配列等に結果を「メモ」しておき、 呼ばれるたびに、すでに探索済みか確認し、探索が終えていれば再帰を行わない。3.動的計画法 漸化式を作る… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fthreestones.hateblo.jp%2Fentry%2F2014%2F06%2F29%2F145755" title="動的計画法part1(ナップザック問題) - ThreeStonesのアレ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2014-06-29 14:57:55 rich https://threestones.hateblo.jp/entry/2014/06/29/145755 1.0 100%