店に入り、いくつかの製品を選択し、カウンターに行って請求書を支払います。合計はいくらかです ( A)。財布、ハンドバッグ、またはポケットに手を伸ばして現金 ( P)を入れPますA。
流通している一連の硬貨と紙幣を考えると、 の最も可能性の高い値はP何ですか?
使用可能な紙幣が $5、$10、$20、$50、および $100 であり、使用可能な硬貨が 5c、10c、および 25c であると仮定した例:
A= $151.24 P[1]= $160 (8x$20) または ($100 + 3x$20) P[2]= $155 ($100 + $50 + $5)
A= $22.65 P[1]= $25 ($20 + $5) P[2]= $30 ($20 + $10) P[3]= $40 ($20 + $20)
A= $0.95 P[1]= $1 (4 x 25c) P[2]= $5
これらの数値の多くは直感的に見えますが、アルゴリズムを特定するのは難しいと感じています.
他の要因もあります。6x0.25で支払う可能性は低く、代わりに1x1.00と2x0.25を使用します。一般に、0.25は3以下、0.10は2以下、0.05は1以下になります。
また、現実の世界では、多くの人が1.00未満の値を気にすることはなく、彼らは手形で支払い、「変化を維持」します。
同じことが5.00、10.00、および20.00にも当てはまります。数ドルを超える購入の場合、代わりに5.00または10.00を使用します。もちろん、ATM機のおかげで20.00が最も一般的に流通しています。
このソフトウェアは何のためにありますか？実際に実際の購入をモデル化して正確な結果が必要ですか、それとも厳密である必要のない単純なシミュレーションが必要ですか？
これは実際には既知の問題であり、私が間違っていなければ、ビンパッキングの変種です...
キャッシャーアルゴリズム（または欲張りアルゴリズム）と呼ばれることもあります。このプレゼンテーションで実装を見つけることができます：http ： //www.cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf、11/12/13ページを参照してください。
（明確にするために、通常のレジ係のアルゴリズムは、顧客に返済するために必要な最小限のコインのみを返します。ただし、動的計画法ソリューションを変更して、可能なすべての組み合わせを計算することができます）
「おそらく」は、これを非常にトリッキーな問題にします。各タイプの通貨の相対的な可用性と分布を知る必要があります。たとえば、流通しているすべての紙幣の 22% は 20 ドルであり、10 ドルから 100 ドルの間の金額で 10 ドルまたは 50 ドルの紙幣よりもはるかに使用される可能性が高くなります。
私は実際にこれを実装することになった人だったので、最終結果を投稿するのが最善だと思いました。きれいではありませんが、高速で、ループや配列はありません。私はこれを概念的な問題の解決策とは考えていませんが、実際の問題は解決しています。
ほとんどの場合、実際の使用量は5ドルから200ドルの範囲に制限されています。ほとんどの人は通常、定期的に500ドルの現金を引き出すことはありません:)
私は$0から$5、$5から$10までのさまざまなケースを検討することにしました。。。45ドルから50ドル。3つのボタンがあったので、いずれの場合も、最初のボタン（最低）は価格の次の5ドルの値になります。したがって、7.45ドルの場合、最初のボタンは8ドル、13.34ドル-> 15ドル、21.01ドル->25ドルでした。
これにより、2番目と3番目のボタンが残ります。5ドル、10ドル、20ドル、50ドルの請求書の標準値を考えると、それぞれのケースには明白な答えがあります。例：$ 24.50を見て、1-> $ 25、2-> $ 30、3->$40。これらは、表といくつかの常識を使用して見つけることができます。
また、50ドルを超える値を使用すると、50ドル未満の値と単純に一致する可能性があることもわかりました。つまり、$72.01は$22.01と同じ答えになります。唯一の注意点は、60より大きく70未満の数字です。その場合、4つの$20の請求書の可能性を処理する必要があります。
アルゴリズムはまた、100ドルから200ドルの範囲にうまくスケーリングします。その上は小売業ではまれなケースです。
POSシステム用です。最終価格を計算するとき、レジ係は顧客から提供された現金の金額を入力する必要があります。レジ係の生活を楽にするために「ありそうな」金額に設定する必要がある3つの「ショートカット」ボタンがあります。絶対的な完璧は必要ありません。– eJames（11月19日22:28）
これには完璧なアルゴリズムはないと思います。私があなたなら、多数の現金取引の既存のPOSデータのソースを見つけて、特定の価格範囲でそれを評価します。人々が通常特定の範囲の価格に対してどのように支払うかを見つけ（正確な変更がはるかに可能性が高い）、最も差別化された範囲に最適な式を考え出します。
OH！@＃$％^＆*（）_、今私は本当にpi..edです。
擬似コードと複雑さの見積もりを10分間書いたところ、投稿すると「私は人間です」というボタンだけが表示され、何かを入力する機会がなく、投稿全体が消えてしまいました（もちろん、今回は作成しませんでした）。念のため、編集ウィンドウのコピー...）、わかりました。短いバージョンを次に示します。
コインの数は通常超単調であるため（つまり、各値は前の値の合計よりも大きい）、貪欲を使用してAの正確なコインを取得できます。
次に、このマルチセットPのコインを使用して、（これまでは空だった）結果セット（マルチセットのセット）と（これまでは空だった）ワーキングセットに追加します。
次に、ワーキングセットが空になるまで繰り返します。
Pの各コインcについて、ワーキングセットからセットPを取り出します。P'= P.replace（c、nextBiggerCoin）、removeSmallestCoin（最小のコインがないPである限り> A）
P'がまだ結果セットに含まれていない場合は、結果セットとワーキングセットに入れます
私が推測した複雑さはO（s * n ^ 2）で、sは解の数です。