もし新しい硬貨を発行するなら、何円硬貨を発行すれば支払いで払う枚数が一番減りますか？

質問

現在、日本で一般的に使用されている硬貨は
1円、5円、10円、50円、100円、500円の6種類だと思いますが、
もし、新しい硬貨を発行するとして、何円硬貨を発行すれば
1～999円のそれぞれの支払いに必要な硬貨の合計枚数が最も減るでしょうか？

ただし、新しい硬貨は999円以下の自然数とし、
支払いは、必ず合計枚数が最も少なくなるような組み合わせで払うとします。

私が計算したところ、意外な結果が出たので、
もしよろしければ、皆さんの結果を教えて下さい。

回答No.10

Tacosan · ベストアンサー

この手の問題はだいたい NP-困難なので多項式時間でまともに解くのは難しいんですが, 常套手段として動的計画法 (Dynamic Programming, DP) というのがあります.
で, DP で解いてみました. 以下, 手元のプログラムが間違っていないという前提でいきます.
少ない方のトップ5 は
117円: 5630枚
133円: 5637枚
112円: 5642枚
121円, 88円: 5642枚
でした. 166円硬貨だと 5657枚で, 183円硬貨と並んで 11位タイ.
えっと.... こんな硬貨, どうやって使えばいいんでしょうか?
ちなみに 1000円硬貨まで許して 10000円までで数えると 917円硬貨を追加したときの 106,604枚がベストの模様. 499円硬貨までだと 479円硬貨の 131,309枚がベストっぽい感じですが, 実は 1000円硬貨を追加する方が (120,000枚なので) よかったりします.

お礼

回答ありがとうございます。
動的計画法は巡回セールスマン問題などで聞いたことがありましたが、すっかり忘れていました。

> えっと.... こんな硬貨, どうやって使えばいいんでしょうか?
たしかに、117円硬貨なんて、使いこなせる人はいないかもしれませんね。
そこで、普通の人でも使いこなせて、比較的、合計枚数が少なくなる硬貨を考えてみました。
111円硬貨なんてどうでしょう？意外と扱いやすくないですか？

答えを教えて頂き、ありがとうございました。お陰でスッキリしました。

回答No.4

cocomonchi

やっぱり１円台を減らすべきなので
３円玉か４円玉だと思います。

回答No.3

noboru0510

感覚的な答えで申し訳ありませんが2円硬貨ではないでしょうか。

下一桁が2円、4円、7円、9円の場合、全てで1円硬貨を半減できますから。

補足

私も最初2円硬貨だと思いました。
私のシミュレーション結果では、２円硬貨では－800枚でした。
（私のシミュレーション自体が間違えている可能性もあるのであしからず）

回答No.2

chirashizushi

８円硬貨

補足

8円硬貨を発行することによって、合計で何枚減らすことが出来ましたでしょうか？

私の計算では、600枚減る結果になりました。

回答No.1

Tacosan

ん～, 今発行されているものを無視して新たに発行するんだったら, 2のベキでいくのが合理的っぽいけど....
ちょっと問題があいまいな感じがします. 新たに発行するのは 1種類なのか複数種類なのか, 今発行されているものに加えて発行するのか今発行されているものは無視するのか, はたまた「良い」とする判断基準はどうなっているのか, などが明確になってません.

補足

前提が足りなくてスミマセン。
既に何となく予想していると思いますが、
新たに発行するのは、現在の6種類に加えて、あともう1種類です。
したがって、支払いで、現在発行されている硬貨も使って構いません。

「良い」と判断する基準は、
1円
2円
3円
…
998円
999円
を払うときに、それぞれの値段で必要な硬貨の総枚数を求めて、それらの合計が最も少なくなる場合と考えてください。