Problem
500,100,50,10,5,1円硬貨をa,b,c,d,e,f枚ずつ持っていたとする。
V円の商品を購入するとき、支払う硬貨の数が最小になるときの枚数を答えよ。支払えない場合は-1を表示するものとする
貪欲法
貪欲法 - Wikipedia
その場での最適選択をするだけで実現できるというもの。
今回の場合は価値の高い硬貨の評価が高いことになる。あとはこれを支払いが終了するまで順番に払い続けていくだけで良い
状態を保持する変数を作るなを持っていれば行ける
scalaの末尾再帰最適化が気になったのでついでにJD-GUIで展開したコードも載せてある。
scala greedy algorithm
