chiwawa_star https://blog.hatena.ne.jp/chiwawa_star/ C++競プロ学習日記(仮) https://chiwawa-star.hatenablog.com/ 動的計画法 DP 配列を- INF で埋めた DP が解らなかったのでナップザック問題を使って比較してみました。使う問題はこれ：ナップザック問題 | 動的計画法 | Aizu Online Judge ① 普通に普通の 埋めDP まずは普通に本 *1 で学習したナップザックで解きます。 定義 dp[ i 個の荷物を考慮して ][ 重さが j 以下のとき ] := 達成可能な価値の和の最大値 のとき 個の荷物を考慮したとき、ナップザックには何も入っていないので重さ ，価値の和も となる。 重さ ，価値 の状態は任意の に対して｢重さ 以下｣の条件を満たすため、任意の に対して dp[ 0 ][ j ] :=… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fchiwawa-star.hatenablog.com%2Fentry%2F2018%2F04%2F21%2F204628" title="いろいろなDP｜動的計画法｜ナップザック - C++競プロ学習日記(仮)" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20i%20-%201 Hatena Blog https://hatena.blog 2018-04-21 20:46:28 rich https://chiwawa-star.hatenablog.com/entry/2018/04/21/204628 1.0 100%