アルゴリズムでこんな出題ありますか？-最適なおつりをもらうための提示貨幣内訳計算

質問

こんばんは。秋の試験を目指して勉強中です。
アルゴリズムの問題でいくつか過去問を理解している最中ですが、
自分でも「問題解決」のためのアルゴリズムをイメージしたりして
慣れています。

ふと「こんな問題あったら面白い」と思うものを考え付きました。
もし類似の設題（プログラミングでも可）あったらご紹介いただくと幸いです。
問：おつり最適化プログラム
レジにて、合計金額に対し、どのような通貨の組み合わせで金額を提示すれば、つり銭をもらったあとの財布の中の貨幣枚数がもっとも少なくなるか、についてプログラムを組んでみよ。

例）購入金額が378円であったが、財布には、
1000円札1枚と、50円玉1枚と、10円玉3枚と、5円玉1枚と、1円玉4枚がある（計10）
答え：1000円札*1、50円玉*1、10円玉*2、5円玉*1、1円玉*3
おつりが、500*1、100*2
残りの貨幣：10円玉*1、1円玉*1
合計：5枚
＊なお、財布の中身　＞　購入金額という条件をクリアしたものとする
お店のレジの貨幣状況（1万円お断り）などの個別の条件は発生しないものとする。購入者の貨幣取り出しの手間隙は考慮しない。
もしくは、このような計算のノウハウはすでに確立されているのでしょうか？

素人の思いつきにお付き合いくだされば幸いです。

回答No.1

say2005 · ベストアンサー

金種計算ですね。
http://www18.ocn.ne.jp/~hkatomc/
の1105番の問題はどうでしょうか。

質問に書いてなかったので
基本情報の問題だろうなと勝手に解釈しました。

この問題はCですが、そのままアルゴリズムの問題にすれば十分応用できると思います。

お礼

ありがとうございます。
基本情報です。失礼しました。
想定している問題ととても近いのでじっくりとトレースしてみます。