주어진 가격에 대한 "일반적인"현금 지불 금액을 결정하는 알고리즘

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 x 25c)
P[2] = $5

이 숫자 중 다수는 직관적 인 것처럼 보이지만 알고리즘을 고정하기가 어렵다는 느낌이 들었습니다.

Answer 1

다른 요인도 있습니다. 6 x 0.25로 지불하지 않을 가능성이 높으며 대신 1 x 1.00 및 2 x 0.25를 사용합니다. 일반적으로 0.25는 더 이상 3, 0.10은 2 세 미만이 아니며 0.05는 더 이상 1이 될 것입니다.

또한 현실 세계에서 많은 사람들이 1.00 미만의 가치를 귀찮게하지 않으며, Alawys는 청구서로 지불하고 "변경을 유지"합니다.

구매에 대해서는 5.00, 10.00 및 20.00에 동일하게 적용됩니다. 물론 ATM 기계 덕분에 20.00은 순환에서 가장 흔합니다.

이 소프트웨어는 무엇입니까? 실제로 모델 실제 구매를 시도하고 있으며 정확한 결과 또는 엄격 할 필요가없는 간단한 시뮬레이션이 필요합니까?

Answer 2

"대부분"은 이것을 매우 까다로운 문제로 만듭니다. 각 통화 유형의 상대적 가용성과 분포를 알아야합니다. 예를 들어, 순환하는 모든 청구서의 22%는 $ 20이므로 $ 10에서 $ 100 사이의 금액에 대해 $ 10 또는 $ 50 지폐보다 훨씬 더 많이 사용될 가능성이 높습니다.

Answer 3

이것은 실제로 알려진 문제입니다. 변형입니다. 빈 포킹 내가 틀리지 않는 경우...

때로는 계산원 알고리즘 (또는 욕심 많은 알고리즘). 이 프레젠테이션에서 구현을 찾을 수 있습니다. http://www.cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf , 페이지 11/12/13을 참조하십시오 ..

(명확히하기 위해, 일반 계산원 알고리즘은 고객에게 지불하는 데 필요한 최소한의 코인 만 반환합니다. 그러나 가능한 모든 조합을 계산하기 위해 동적 프로그래밍 솔루션을 변경할 수 있습니다).

Answer 4

오!@#$%^&*() _, 이제 나는 정말로 pi..ed입니다.

방금 10 분 동안 의사 코드와 복잡성 추정을 썼습니다. 게시 할 때 "I Human '"버튼 만 있습니다. 만일을 대비하여 편집 창의 사본 ...), 여기에 짧은 버전이 있습니다.

동전의 수는 일반적으로 슈퍼 모노톤 (즉, 각 값은 이전 값의 합보다>)이므로 욕심을 사용하여 A의 정확한 동전을 얻을 수 있습니다.

이제이 멀티 세트의 동전을 사용하여 (지금까지 비어있는) 결과 세트 (멀티 세트 세트) 및 (지금까지 비어있는) 작업 세트에 추가하십시오.

이제 작업 세트가 비어있을 때까지 반복하십시오.

P : P '= P.Replace (C, NextBiggerCoin)의 각 동전 C에 대해 작업 세트 P'= P에서 P를 세우십시오.

P '가 아직 결과 세트에 있지 않은 경우 결과 세트 및 작업 세트에 넣으십시오.

내가 추측 한 복잡성은 O (s*n^2)였으며, 솔루션의 수는 s입니다.

Answer 5

시점 시스템을위한 것입니다. 최종 가격이 계산되면 계산원은 고객이 제공 한 현금 금액을 입력해야합니다. 계산원의 삶을 더 쉽게하기 위해 "가능성"금액으로 설정 해야하는 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-> $ 15, $ 21.01-> $ 25였습니다.

이것은 두 번째와 세 번째 버튼을 남깁니다. 각 사례에는 $ 5, $ 10, $ 20, $ 50 지폐의 표준 가치가 주어지면 명백한 답변이 있습니다. 예 : $ 24.50을보고 1-> $ 25, 2-> $ 30, 3-> $ 40. 이것들은 테이블과 상식을 사용하여 찾을 수 있습니다.

또한 값을 사용하면 50 달러가 50 달러 이하로 단순히 50 달러 미만의 상대와 일치 할 수 있습니다. IE : $ 72.01은 $ 22.01 등과 같은 답변이 될 것입니다. 유일한 경고는 60보다 크고 70보다 작은 숫자입니다.이 경우 4 달러 지폐의 가능성을 처리해야합니다.

알고리즘은 또한 $ 100 ~ $ 200 범위의 범위로 잘 조정됩니다. 그 위에는 소매점에서 드문 경우입니다.