食費を節約するために動的計画法を用いる
問題
C: 節制 - AtCoder Beginner Contest 013 | AtCoder
はじめ、高橋君の満腹度は H です。N 日間のそれぞれの日について、その日にとる食事を次の 3 種類の中から 1 つ選びます。
普通の食事: A 円の出費をして、満腹度が B 増える。
質素な食事: C 円の出費をして、満腹度が D 増える。
食事抜き: 出費なしで、満腹度が E 減る。
厳しく節約すれば出費を抑えることができますが、あまりに節約しすぎて体調を崩してしまってはいけないため、N 日間で一度も満> > 腹度が 0 以下にならないようにしなければなりません。
高橋君は最低何円の食費で N 日間を乗り切ることができるでしょうか？
ソースコード(40点解法)
今回は動的計画法を学ぶために40点解法を載せます。
解説
簡単に解説します。
動的計画法を使おう
普通に全探索すると、1.普通の食事, 2.質素な食事, 3.食事抜きの３パターンを選ぶ事をN回行うことになる。 すると計算量はO(3N)となり莫大。
そこで動的計画法を用いることで計算量を減らす方法を考える。この解法であれば40点はもらえる。
この問題を整理する。
求めたい値: 最小の出費
保持する値: 何日目か(day)、残りの体力は(life)
そして、以下のような再帰関数を作る
day日目が終わった段階で満腹度がhという状態に至る最小の費用を計算するものである。
このコードは30点解答である。 一番上にあげたコードは、動的計画法するにあたり保持する値(今回はday, life)が２つ以上の場合、その値をクラスのインスタンス変数として管理しているものだ。
ポイント
今回は、「普通の食事」「質素な食事」「食べない」という選択肢の中で毎日どれかを選択し、ｎ日間過ごす。そして最終的に費用が最小の物を算出する。基本的には、毎日３パターンを試す方法だが、その時に過去に計算した結果が使えれば、その計算結果を再利用し、同じ計算を２度と行わないようにする。こうすることで計算量を減らすことができる。
