基于面额,为特定价格支付的算法可能金额(超过)

Question

在当前的项目中,人们可以订购送货上门的货物并选择"付款时付款"作为付款选项.为了确保交付人员有足够的变化,客户被要求输入他们将支付的金额(例如交付48,13,他们将支付60, - (3*20, - )).现在,如果它取决于我,我会把它变成一个自由的领域,但是已经决定应该是基于可用面额的选择,而不给出会导致一组可能更小的面额的金额.

例:

denominations = [1,2,5,10,20,50]
price = 78.12
possibilities:
    79  (multitude of options),
    80  (e.g. 4*20)
    90  (e.g. 50+2*20)
    100 (2*50)

它是国际的,所以面额可能会改变,算法应该基于该列表.

我最接近的似乎是有效的:

for all denominations in reversed order (large=>small)
    add ceil(price/denomination) * denomination to possibles
    baseprice = floor(price/denomination) * denomination;
    for all smaller denominations as subdenomination in reversed order
        add baseprice + (ceil((price - baseprice) / subdenomination) * subdenomination) to possibles
    end for
end for
remove doubles
sort

是,似乎工作,但这已经出现后疯狂地尝试各种紧凑的算法,我不能捍卫为什么它的工作原理,这可能导致一些边缘情况下/新的国家得到错误的选项,它确实产生一些严重的金额双打.

因为这可能不是一个新问题,谷歌等人.无法为我提供答案除了计算如何进行精确更改的大量页面之外,我想我会问:你之前解决了这个问题吗？哪种算法？任何证据都会一直有效吗？

Answer 1

它是贪心算法的应用http://mathworld.wolfram.com/GreedyAlgorithm.html（一种用于从尽可能小的组成部分递归构造一组对象的算法）

伪代码

list={1,2,5,10,20,50,100} (*ordered *)
while list not null
   found_answer = false
   p = ceil(price) (* assume integer denominations *)
   while not found_answer
      find_greedy (p, list) (*algorithm in the reference above*)
      p++
   remove(first(list))

编辑>一些迭代是无意义的>

list={1,2,5,10,20,50,100} (*ordered *)
p = ceil(price) (* assume integer denominations *)
while list not null
   found_answer = false
   while not found_answer
      find_greedy (p, list) (*algorithm in the reference above*)
      p++
   remove(first(list))

编辑>

我发现皮尔逊对贪婪算法的改进。其 O(N^3 log Z)，其中 N 是面额数，Z 是该组钞票中最大的钞票。

您可以在http://library.wolfram.com/infocenter/MathSource/5187/中找到它