基于面值的特定价格支付的算法可能的金额（大于）

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 

是似乎工作，但这已经出现后疯狂地尝试各种紧凑的算法，我不能捍卫为什么它有效，这可能会导致一些边缘/新的国家出现错误的选择，并且确实会产生大量的双打。

由于这可能不是一个新问题，而Google等人。除了大量的页面计算如何进行确切的改变之外，我无法给出答案，我想我会问：你之前是否解决过这个问题？哪种算法？任何证明它将始终有效？

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)) 

EDIT>一些迭代是无义>

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)) 

EDIT>

我发现的改善由于皮尔逊的贪婪算法。它的O（N^3 log Z），其中N是面额的数量，Z是该组的最大账单。

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

Answer 2

您可以在数据库中生成payd硬币和纸张的所有可能的组合集合（im英语不好），每行包含这个组合的总和。

有了这个数据库，你可以简单的获得所有可能通过一个查询买贵了，

WHERE sum >= cost and sum <= cost + 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];