この記事で使うアルゴリズム
動的計画法
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=ja
この問題は動的計画法を用いて解くことができます。
方針
dp[n][w]
を考えます。このリストは重さの総和がw以下となるようにn番目までの品物を選んだ時の価値の最大値
を表します。
コード
DPL1B 0-1ナップザック問題とほとんど同じコードになります。
貰うDP
1 | dp[n+1][w-wn] |
dp[n+1][w-wn]
が配列外参照になるかの判定が必要です。
1 | N, W = map(int, input().split()) |
配るDP
1 | dp[n][w] ----->dp[n+1][w] |
DP配列を大きめに確保することで、配列外参照を気にする必要がありません。
1 | Wmax = 1000 |
DPL1B 0-1ナップザック問題と違いw
を逆にループさせることはできません。
記事情報
- 投稿日:2020年5月13日
- 最終更新日:2020年5月14日