خوارزمية لتحديد "المعتادة" دفع المبالغ النقدية لسعر معين

Question

ويمكنك المشي الى متجر، حدد العديد من المنتجات، ثم انتقل إلى وصفة طبية لدفع الفاتورة. ويبلغ مجموع قدرا (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 × 25C)
P[2] = $ 5

وكثير من هذه الأرقام تبدو بديهية، ولكن لدي شعور بأن الخوارزمية من الصعب تحديد ماهيتها.

Answer 1

وهناك أيضا عوامل أخرى، أنت ليس من المرجح أن يدفع مع 6 × 0.25، يمكنك استخدام 1 × 1.00 و 2 × 0.25 بدلا من ذلك. عموما 0.25 لن يكون هناك أكثر من 3، فإن 0،10 يكون هناك أكثر من 2، و 0.05 لن يكون هناك أكثر من 1.

وأيضا في العالم الحقيقي، وكثير من الناس لا تهتم القيم أقل من 1.00، وalawys تدفع مع فواتير و "الحفاظ على التغيير".

ينطبق

ونفس إلى 5.00، 10.00، 20.00 و، لشراء أكثر من بضعة دولارات الناس سوف تستخدم 5.00 أو 10.00 بدلا من ذلك. بالطبع 20.00 هي الأكثر شيوعا في التداول وذلك بفضل أجهزة الصراف الآلي.

ما هو هذا البرنامج ل؟ وكنت في الواقع محاولة نموذج الشراء الفعلية وتحتاج نتائج دقيقة، أو محاكاة البسيطة التي لا يجب أن يكون دقيقا؟

Answer 2

و"على الأرجح" يجعل هذه مشكلة صعبة للغاية. كنت بحاجة لمعرفة مدى توافر النسبي وتوزيع كل نوع العملة. على سبيل المثال، 22٪ من جميع مشاريع القوانين المتداولة هي $ 20S، مما يجعلها أكثر عرضة ليتم استخدامها من 10 $ أو 50 $ فواتير بمبالغ تتراوح بين 10 $ و 100 $.

Answer 3

وهذا هو في الواقع مشكلة معروفة، انها البديل من binpacking إذا لم أكن مخطئ ...

في بعض الأحيان انها تسمى خوارزمية الصرافين (أو الجشع خوارزمية ). يمكنك العثور على تنفيذها في هذا العرض: HTTP: // شبكة الاتصالات العالمية. cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf ، راجع صفحة 11/12/13 ..

و(لتوضيح، الخوارزمية الصراف العادية يعود فقط الحد الأدنى من القطع النقدية اللازمة لدفع العملاء إلى الوراء، ولكن هل يمكن أن تغيير الحل البرمجة الديناميكية لحساب جميع التوليفات الممكنة)

Answer 4

وOH! @ # $٪ ^ & * () _، الآن أنا pi..ed حقا.

ولقد كتب شبة الكود وتقدير تعقيد لمدة 10 دقيقة، وعندما أقوم بنشر هناك فقط على زر "أنا إنسان" من دون أي فرصة لإدخال شيء وذهب منصبي كاملة (وبطبيعة الحال، وهذه المرة لم يجعل نسخة من إطار التحرير، فقط في حالة ...)، طيب حتى هنا هي مقطعة:

وعدد من العملات المعدنية عادة سوبر روتيني (أي كل قيمة هي> من مجموع القيم السابقة)، لذلك يمكنك استخدام الجشع للحصول على القطع النقدية الدقيقة لA.

والآن استخدام هذه المجموعة P متعددة من القطع النقدية، وإضافته إلى (حتى الآن فارغ) مجموعة النتائج (مجموعة من MULTISETS)، وإلى (ما يصل الى فارغة جدا الآن) مجموعة العمل.

والآن كرر حتى مجموعة العمل فارغ:

واتخاذ مجموعة P من مجموعة العمل، P '= P، لكل عملة ج في P: P' = P.replace (ج، nextBiggerCoin)، removeSmallestCoin (طالما P دون أصغر عملة لا يزال> A)

وإذا كان P "ليست بعد في مجموعة النتائج، ووضعها في مجموعة نتيجة ومجموعة العمل

وكان لي تعقيد تفكر O (ق * ن ^ 2)، مع الصورة عدد من الحلول.

Answer 5

<اقتباس فقرة>   

وهو الحال بالنسبة لنظام نقطة البيع. عندما يتم احتساب السعر النهائي، أمين الصندوق أن تدخل في المبالغ النقدية التي يقدمها العملاء. هناك ثلاثة أزرار "اختصار" التي يجب تعيينها إلى المبالغ "المحتمل" لجعل الحياة أسهل أمين الصندوق. الكمال المطلق ليست ضرورية. - eJames (19 نوفمبر في 22:28)

وأنا لا أعتقد أن هناك خوارزمية مثالية لهذا الغرض. إذا كنت أنت، وأود أن تجد مصدرا للبيانات POS الحالية لعدد كبير من المعاملات النقدية وتقييم أن أكثر من نطاقات معينة للأسعار. البحث عن كيف يمكن للناس تدفع عادة لنطاقات محددة من الأسعار (التغيير الدقيق هو أكثر بكثير من المرجح)، والعمل على وضع صيغة أفضل لائقا للنطاقات الأكثر متباينة.

Answer 6

وكنت فعلا الشخص الذي انتهى تنفيذ هذا واحد حتى ظننت أنه من الأفضل لنشر النتيجة النهائية. انها ليست جميلة ولكنها سريعة وليس لديها أي حلقات أو صفائف. أنا لا أعتبر هذا حل للمسألة المفاهيمي لكنه لا يحل المشكلة العملية.

في معظم الحالات، يقتصر الاستخدام الفعلي لمجموعة $ 5 إلى $ 200. معظم الناس لا سحب عادة من 500 $ نقدا على أساس منتظم:)

وقررت أن ننظر في الحالات المختلفة من $ 0-5 $، 5 $ إلى 10 $. . . $ 45 $ 50. كان لدينا 3 أزرار وذلك في كل حال، فإن الزر الأول (الأدنى) سيكون القادمة قيمة $ 5 فوق السعر. حتى إذا كان $ 7.45 ثم 8 $ كان الزر الأول، 13.34 $ -> $ 15، $ 21.01 -> $ 25

وهذا يترك أزرار 2ND و 3rd. فلكل حالة إجابات واضحة نظرا لالقيم القياسية من 5 $، 10 $، 20 $، 50 $ الفواتير. على سبيل المثال: عند النظر إلى 24.50 $ ثم 1 -> 25 $، 2 -> $ 30، 3 -> $ 40. يمكن العثور على هذه باستخدام الجدول وبعض الحس السليم.

ولقد وجدت أيضا أن استخدام قيم أكبر $ 50 يمكن ببساطة مطابقة ما دون 50 $ نظرائهم. أي: $ 72.01 سيكون الجواب نفسه كما 22،01 $، وهلم جرا. التحذير الوحيد هو مع أعداد أكبر من 60 وأقل من 70. وهذه القضية تتطلب التعامل مع امكانية 4 $ 20 الفواتير.

والخوارزمية أيضا تحجيم بشكل جيد في نطاق 100 $ إلى 200 $. فوق ذلك هو حالة نادرة في مجال تجارة التجزئة.