問題

解き方

全列挙する場合、i番目の薬品を購入する場合としない場合を２パターンをN回行うので、計算量はO(2^N)となりNは最大40なので間に合わない。

dp(i, x, y)を以下のように定義する。

dp(i, x, y) := {i番目までの薬を使用した時、物質aの和がx, bの和がyとなる、最小コスト}

dp(i, x, y)は漸化式を用いて次のように表す事ができる。

dp(i, x, y) = min(dp(i - 1, x, y), dp(i - 1, x - a[i], y - b[i]) + cost[i])

後は配列のインデックスがOutOfRangeしないようにfor文を回してあげる。するとi に N - 1 を代入したdp[N - 1][x][y]は、全ての薬品を考慮した時のx, yのコストを取得することができる。あとは、与えられた比となるx, yを見ていき最小コストを出力してあげる。