Thuật toán để xác định số tiền thanh toán bằng tiền mặt "bình thường" cho một mức giá nhất định

Question

Bạn đi bộ vào một cửa hàng, chọn một số sản phẩm, sau đó truy cập vào thanh toán để thanh toán hóa đơn của bạn. Tổng số tiền là một số tiền (A). Bạn tiếp cận ví, ví hoặc túi của bạn và đặt xuống một số tiền mặt (P), trong đó P> = A và nhân viên thu ngân cho bạn thay đổi.

Với tập hợp tiền xu và hóa đơn đang được lưu hành, các giá trị có khả năng nhất cho P là gì?

Một số ví dụ, giả định rằng các hóa đơn có sẵn là $ 5, $ 10, $ 20, $ 50 và $ 100, và các đồng tiền có sẵn là 5c, 10c và 25c:

A = $ 151,24
P[1] = $ 160 (8x $ 20) hoặc ($ 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

Nhiều người trong số những con số này dường như trực giác, nhưng tôi có cảm giác rằng các thuật toán rất khó để pin xuống.

Answer 1

Ngoài ra còn có các yếu tố khác, bạn không có khả năng thanh toán với 6 x 0,25, bạn sẽ sử dụng 1 x 1,00 và 2 x 0,25 thay thế. Nói chung 0,25 sẽ không còn sau đó 3, 0,10 sẽ không được nhiều hơn sau đó 2, và 0,05 sẽ không nhiều hơn sau đó 1.

Ngoài ra trong thế giới thực, nhiều người không bao giờ bận tâm với các giá trị ít hơn 1,00, họ alawys trả tiền với hóa đơn và "giữ nguyên thay đổi".

Tương tự áp dụng cho 5,00, 10,00 và 20,00, đối với các giao dịch mua nhiều hơn thì một vài đô la sẽ sử dụng 5,00 hoặc 10,00 thay thế. Tất nhiên 20.00 là phổ biến nhất trong lưu thông nhờ máy ATM.

Phần mềm này là gì? bạn có thực sự đang cố gắng mua hàng thực tế mô hình và cần kết quả chính xác hoặc mô phỏng đơn giản không cần phải nghiêm ngặt không?

Answer 2

OH! @ # $%^& *() _, bây giờ tôi thực sự là pi..ed.

Tôi vừa viết ước tính giả và phức tạp trong 10 phút, và khi tôi đăng bài chỉ là nút "Tôi là con người" mà không có cơ hội để nhập nội dung nào đó và bài đăng hoàn chỉnh của tôi đã biến mất (và tất nhiên, lần này Tôi không tạo bản sao của cửa sổ chỉnh sửa, chỉ trong trường hợp ...), ok, vậy đây là phiên bản ngắn:

Số tiền xu thường là siêu đơn điệu (tức là mỗi giá trị> tổng giá trị trước đó), do đó bạn có thể sử dụng tham lam để có được số tiền chính xác cho A.

Bây giờ hãy sử dụng tập hợp P nhiều tiền xu này, thêm nó vào tập kết quả (đến hết) kết quả (một tập hợp nhiều) và lên (lên) để trống bây giờ) làm việc thiết lập.

Bây giờ lặp lại cho đến khi thiết lập làm việc trống:

Đưa bộ P ra khỏi thiết lập làm việc, P '= P, đối với mỗi đồng xu c trong P: P' = P.replace (c, nextBiggerCoin), removeSmallestCoin (miễn là P không đồng xu nhỏ nhất vẫn> A)

Nếu P' không phải là nêu ra trong tập kết quả, đặt nó vào tập hợp kết quả và làm việc thiết lập

phức tạp đoán của tôi là O (s * n^2), với s số lượng các giải pháp.

Answer 3

"Rất có thể" làm cho vấn đề này trở nên rất phức tạp. Bạn sẽ cần phải biết sự sẵn có tương đối và phân phối của từng loại tiền tệ. Ví dụ: 22% của tất cả các hóa đơn đang lưu hành là 20 đô la, khiến chúng có nhiều khả năng được sử dụng hơn 10 đô la hoặc 50 đô la cho số tiền từ 10 đô la đến 100 đô la.

Answer 4

Đây thực sự là một sự cố đã biết, đó là một biến thể của binpacking nếu tôi không nhầm lẫn ...

Đôi khi được gọi là thuật toán của nhân viên thu ngân (hoặc greedy algorithm). Bạn có thể tìm thấy triển khai trong bản trình bày này: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf, xem trang 11/12/13 ..

(để làm rõ, thuật toán thủ quỹ thông thường chỉ trả lại số tiền tối thiểu cần thiết để trả khách hàng. Nhưng bạn có thể thay đổi giải pháp lập trình động để tính toán tất cả các kết hợp có thể)

Answer 5

Nó dành cho hệ thống điểm bán hàng. Khi giá cuối cùng được tính toán, nhân viên thu ngân phải nhập vào số tiền mà khách hàng cung cấp. Có ba nút "lối tắt" cần được đặt thành số tiền "có khả năng" để giúp cuộc sống của nhân viên thu ngân dễ dàng hơn. Tuyệt đối tuyệt đối là không cần thiết. - eJames (ngày 19 tháng 11 tại 22:28)

Tôi không nghĩ rằng có một thuật toán hoàn hảo cho việc này. Nếu tôi là bạn, tôi sẽ tìm thấy nguồn dữ liệu POS hiện có cho một số lượng lớn giao dịch tiền mặt và đánh giá rằng trên phạm vi giá cụ thể. Tìm cách mọi người thường thanh toán cho các phạm vi giá cụ thể (thay đổi chính xác có nhiều khả năng hơn) và tạo ra một công thức phù hợp nhất cho các phạm vi được phân biệt nhiều nhất.

Answer 6

Tôi thực sự là người đã kết thúc triển khai chương trình này vì vậy tôi nghĩ tốt nhất nên đăng kết quả cuối cùng. Nó không đẹp nhưng nó nhanh và không có bất kỳ vòng lặp hay mảng nào. Tôi không coi đây là một giải pháp cho câu hỏi khái niệm nhưng nó giải quyết vấn đề thực tế.

Trong hầu hết các trường hợp, mức sử dụng thực tế được giới hạn trong phạm vi từ $ 5 đến $ 200. Hầu hết mọi người thường không rút ra $ 500 tiền mặt một cách thường xuyên :)

Tôi quyết định xem xét các trường hợp khác nhau từ $ 0 đến $ 5, $ 5 đến $ 10,. . . $ 45 đến $ 50. Chúng tôi có 3 nút để trong mọi trường hợp, nút đầu tiên (thấp nhất) sẽ là giá trị $ 5 tiếp theo cao hơn giá. Vì vậy, nếu đó là $ 7,45 thì $ 8 là nút đầu tiên, $ 13,34 -> $ 15, $ 21,01 -> $ 25.

Nút này để lại các nút thứ 2 và thứ 3. Mỗi trường hợp có câu trả lời rõ ràng cho các giá trị tiêu chuẩn của $ 5, $ 10, $ 20, $ 50 hóa đơn. ví dụ: Nhìn vào $ 24,50 sau đó 1 -> $ 25, 2 -> $ 30, 3 -> $ 40. Đây có thể được tìm thấy bằng cách sử dụng một bảng và một số ý nghĩa thông thường.

Tôi cũng nhận thấy rằng việc sử dụng các giá trị lớn hơn $ 50 có thể chỉ đơn giản là khớp với dưới 50 đô la của chúng. tức là: $ 72,01 sẽ là câu trả lời giống như $ 22,01, v.v. Lời cảnh báo duy nhất là với số lượng lớn hơn 60 và nhỏ hơn 70. Trường hợp đó yêu cầu xử lý khả năng của 4 hóa đơn $ 20.

Thuật toán cũng quy mô độc đáo trong phạm vi từ $ 100 đến $ 200. Trên đây là một trường hợp hiếm hoi trong bán lẻ.