Matsushita's Blog

食費を節約するために動的計画法を用いる

問題

C: 節制 - AtCoder Beginner Contest 013 | AtCoder

はじめ、高橋君の満腹度は H です。N 日間のそれぞれの日について、その日にとる食事を次の 3 種類の中から 1 つ選びます。

普通の食事: A 円の出費をして、満腹度が B 増える。

質素な食事: C 円の出費をして、満腹度が D 増える。

食事抜き: 出費なしで、満腹度が E 減る。

厳しく節約すれば出費を抑えることができますが、あまりに節約しすぎて体調を崩してしまってはいけないため、N 日間で一度も満> > 腹度が 0 以下にならないようにしなければなりません。

高橋君は最低何円の食費で N 日間を乗り切ることができるでしょうか?

ソースコード(40点解法)

今回は動的計画法を学ぶために40点解法を載せます。

解説

簡単に解説します。

動的計画法を使おう

普通に全探索すると、1.普通の食事, 2.質素な食事, 3.食事抜きの3パターンを選ぶ事をN回行うことになる。 すると計算量はO(3N)となり莫大。

そこで動的計画法を用いることで計算量を減らす方法を考える。この解法であれば40点はもらえる。

この問題を整理する。

求めたい値: 最小の出費

保持する値: 何日目か(day)、残りの体力は(life)

そして、以下のような再帰関数を作る

day日目が終わった段階で満腹度がhという状態に至る最小の費用を計算するものである。

このコードは30点解答である。 一番上にあげたコードは、動的計画法するにあたり保持する値(今回はday, life)が2つ以上の場合、その値をクラスのインスタンス変数として管理しているものだ。

ポイント

今回は、「普通の食事」「質素な食事」「食べない」という選択肢の中で毎日どれかを選択し、n日間過ごす。そして最終的に費用が最小の物を算出する。基本的には、毎日3パターンを試す方法だが、その時に過去に計算した結果が使えれば、その計算結果を再利用し、同じ計算を2度と行わないようにする。こうすることで計算量を減らすことができる。