Jisseikatsu-Algorithm-1-5-3

《DP の配列》
・dp[タイプいくつまで考えたか][値段合計] = (kcal 最大)
・答えは dp[K][L]


《状態遷移》
まず、タイプ i の商品の買い方は以下の c[i]+1 通りしかありません。ただし c[i] = (タイプ i の商品の個数) とします。
・タイプ i の商品をどれか 1 個選び、それを買う。（c[i] 通り）
・タイプ i の商品を買わない。（1 通り）
・それぞれ (カロリー増加分, 値段増加分) = (a[1], b[1]), ..., (a[c[i] + 1], b[c[i] + 1]) とする

したがって、dp[i][?] → dp[i+1][?] の遷移は次の通りです：
・dp[i+1][j] = max(dp[i][j-b[1]]+a[1], dp[i][j-b[2]]+a[2], dp[i][j-b[3]]+a[3], ..., dp[i][j-b[c[i]+1]]+a[c[i]]+1)


《計算量》
計算量は O(L + (c[1] + c[2] + ... + c[K])) = O(NL) となります。