読者です 読者をやめる 読者になる 読者になる

AccessViolation Exception

仕事でもはんだづけ、家でもはんだづけ

scalaで貪欲法で解く問題をやってみる

技術ネタ Scala

Problem


500,100,50,10,5,1円硬貨をa,b,c,d,e,f枚ずつ持っていたとする。

V円の商品を購入するとき、支払う硬貨の数が最小になるときの枚数を答えよ。支払えない場合は-1を表示するものとする

貪欲法


貪欲法 - Wikipedia

その場での最適選択をするだけで実現できるというもの。

今回の場合は価値の高い硬貨の評価が高いことになる。あとはこれを支払いが終了するまで順番に払い続けていくだけで良い

Scala


状態を保持する変数を作るなを持っていれば行ける

scalaの末尾再帰最適化が気になったのでついでにJD-GUIで展開したコードも載せてある。

  • 再帰からループに展開される
    • はやくなるね!

scala greedy algorithm