人権なし

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

Educational DP Contest:E - Knapsack 2

問題

atcoder.jp

解法

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

と定義する.このとき,

dp(i, j) = inf (j < 0 のとき)

dp(i, j) = 0 (j == 0 のとき)

min( dp(i - 1, j) , dp(i - 1, j - v_(i - 1)) + w_(i - 1) ) (それ以外)

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

解答

atcoder.jp

これもメモ化再帰で書いたので少し重い結果になった.

f:id:babcs2035:20190107165203p:plain