Educational DP Contest：D - Knapsack 1
問題
解法
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)．
解答
メモ化再帰で書いたので少し実行時間とメモリ使用量ともに重い結果になった．
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)．
メモ化再帰で書いたので少し実行時間とメモリ使用量ともに重い結果になった．