人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

Educational DP Contest:D - Knapsack 1

問題

atcoder.jp

解法

dp(i, j) := i 番目のものまでで重さ j のときの価値の最大値

と定義する.このとき,

dp(i, j) = max( dp(i - 1, j) , dp(i - 1, j - w_(i - 1)) + v_(i - 1) )

と漸化式が立つ.状態数 O(NW),遷移 O(1) となり O(NW). 

解答

atcoder.jp

メモ化再帰で書いたので少し実行時間とメモリ使用量ともに重い結果になった.

f:id:babcs2035:20190107164720p:plain