代码之家 › 专栏 › 技术社区 › Wrikken

根据面额计算特定价格可能支付的金额(超额)

currency math language-agnostic algorithm

Wrikken · 技术社区 · 14 年前

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

例子:

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

是似乎可以,但这是在疯狂尝试各种紧凑算法之后出现的,我不能保护 为什么? 它起作用,这可能导致一些边缘案例/新国家得到错误的选择,而且它确实产生了一些严重的翻倍。

因为这可能不是一个新问题,谷歌等。除了一大堆计算如何进行精确更改的页面之外,我不能给我一个答案,我想我会问:你以前解决过这个问题吗?哪种算法?有证据证明它总是有效的吗?

2 回复 | 直到 14 年前

Dr. belisarius 14 年前

贪婪算法的应用 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/

Svisstack 14 年前

您可以在数据库中生成所有可能的付费硬币和纸张组合集(我的英语不好),每一行包含此组合的总和。

有了这个数据库,您可以简单地通过一个查询获得所有可能的超额支付,

WHERE sum >= cost and sum <= cost + epsilon

关于epsilon的一些话,嗯……您可以从成本值分配它吗?大概10%的成本加上10美元?:

WHERE sum >= cost and sum <= cost * 1.10 + 10

表结构必须具有表示硬币数量和纸张类型的列数。每列的值都有此类付款项目的发生次数。

这不是这个问题的最佳和最快的解决方案,但易于实现。我想到了更好的解决办法。

你可以从其他方面 cost 到 cost + epsilon 对于每一个价值,计算出每一个支付项目的最小可能数量。我有它的算法。你可以用这个算法做这个,但是这是在C++中:

int R[10000];
sort(C, C + coins, cmp);

R[0]=0;

for(int i=1; i <= coins_weight; i++)
{
    R[i] = 1000000;
    for (int j=0; j < coins; j++) 
    {
        if((C[j].weight <= i) && ((C[j].value + R[i - C[j].weight]) < R[i]))
        {
            R[i] = C[j].value + R[i - C[j].weight];
        }
    }
}

return R[coins_weight];