Educational DP Contest：E - Knapsack 2
問題
解法
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)．
解答
これもメモ化再帰で書いたので少し重い結果になった．
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)．
解答
メモ化再帰で書いたので少し実行時間とメモリ使用量ともに重い結果になった．
Educational DP Contest：C - Vacation
問題
解法
dp(i, j) := i - 1 日目に j を選んだ時の i 日目までの幸福度の和の最大
と定義する．このとき，
dp(i, j) = max( dp(i - 1, 0) + a_(i - 1) (j != 0 のとき), dp(i - 1, 1) + b_(i - 1) (j != 1 のとき), dp(i - 1, 2) + c_(i - 1) (j != 2 のとき))
と漸化式が立つ．状態数 O(N)，遷移 O(1) となり O(N)．
解答
