＆＃8220;通常＆＃8221;を決定するアルゴリズム特定の価格の現金支払い額

Question

店に足を踏み入れて、いくつかの製品を選択し、カウンターに行って請求書を支払います。合計はいくらかの量です（ A ）。財布、財布、またはポケットに手を入れて、現金（ P ）を置きます。ここで、 P ＆gt; = 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ドル

これらの数値の多くは直感的に見えますが、アルゴリズムを特定するのは難しいと感じています。

Answer 1

他の要因もあります。6x 0.25で支払う可能性は低く、代わりに1 x 1.00と2 x 0.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が最も一般的に流通しています。

このソフトウェアの目的は何ですか？実際に実際の購入をモデル化し、正確な結果が必要ですか、それとも厳密でなくてもよい単純なシミュレーションが必要ですか？

Answer 2

＆quot;最も可能性が高い＆quot;これは非常に難しい問題です。各通貨の相対的な可用性と分布を知る必要があります。たとえば、流通しているすべての請求書の22％は20ドルであり、10ドルから100ドルの間の金額で10ドルまたは50ドルの請求書よりもはるかに使用されやすくなっています。

Answer 3

これは実際には既知の問題であり、 binpacking の変種です間違えた...

キャッシャーアルゴリズム（または貪欲アルゴリズム）と呼ばれることもあります。このプレゼンテーションで実装を見つけることができます： http：// www。 cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf 、11/12/13を参照してください。

（明確にするために、通常のキャッシャーアルゴリズムは、顧客に返済するために必要な最小限のコインのみを返します。ただし、動的プログラミングソリューションを変更して、可能なすべての組み合わせを計算できます）

Answer 4

OH！@＃$％^＆amp; *（）_、今私は本当にpi..edになっています。

10分間擬似コードと複雑さの見積もりを書いたところです。投稿するときは、「私は人間です」というボタンだけがあります。何かを入力する機会がなく、私の完全な投稿は消えてしまいます（もちろん、今回は編集ウィンドウのコピーを作成しませんでしたが、念のため...）。

コインの数は通常スーパーモノトーン（つまり、各値は前の値の合計よりも大きい）であるため、貪欲を使用してAの正確なコインを取得できます。

このマルチセットPのコインを使用して、（今まで空だった）結果セット（マルチセットの集合）と（今まで空だった）作業セットに追加します。

ワーキングセットが空になるまで繰り返します：

Pの各コインcについて、ワーキングセットからPを取り出します（P '= P）：P' = P.replace（c、nextBiggerCoin）、removeSmallestCoin（最小のコインがないPがまだ＆gt;である限り）

P 'がまだ結果セットにない場合は、結果セットと作業セットに入れます

推測された複雑さはO（s * n ^ 2）で、sは解の数でした。

Answer 5

  

これはPOSシステム用です。最終価格が計算されると、レジ係は顧客から提供された現金の金額を入力する必要があります。 3つの「ショートカット」があります。 「可能性が高い」に設定する必要があるボタンレジ係の生活を楽にします。完全な完成度は必要ありません。 – eJames（11月19日22:28）

これには完璧なアルゴリズムはないと思います。私があなたなら、多数の現金取引の既存のPOSデータのソースを見つけて、特定の価格帯で評価します。特定の範囲の価格に対する人々の通常の支払い方法を見つけ（正確な変更ははるかに可能性が高い）、最も差別化された範囲に最適な式を計算します。

Answer 6

私は実際にこれを実装することになったので、最終結果を投稿するのが最善だと思いました。きれいではありませんが、迅速で、ループや配列はありません。私はこれを概念的な問題の解決策とは考えていませんが、実際的な問題を解決します。

ほとんどの場合、実際の使用は5〜200ドルの範囲に制限されています。ほとんどの人は通常500ドルを定期的に現金で引き出すことはありません：）

$ 0から$ 5、$ 5から$ 10などのさまざまなケースを調べることにしました。 。 。 45〜50ドル。ボタンが3つあるので、どの場合でも、最初のボタン（最低）は価格を超えた次の5ドルの値になります。したがって、7.45ドルの場合、最初のボタンは8ドル、13.34ドル-＆gt; $ 15、$ 21.01-＆gt; 25ドル。

これにより、2番目と3番目のボタンが残ります。各ケースには、5ドル、10ドル、20ドル、50ドルの請求書の標準値を与えられた明らかな回答があります。例：24.50ドルを見てから1-＆gt; $ 25、2-＆gt; $ 30、3-＆gt; $ 40。これらは、表といくつかの常識を使用して見つけることができます。

また、50ドルを超える値を使用すると、50ドル未満の値と単純に一致することもわかりました。つまり、$ 72.01は$ 22.01と同じ答えになります。唯一の注意点は、数字が60を超え70未満である場合です。その場合、4つの20ドル札の可能性を処理する必要があります。

このアルゴリズムは、100ドルから200ドルの範囲にうまくスケールします。上記は小売店ではまれなケースです。