硬币找零优化

Question

我试图解决这个问题：

假设我有一组N个硬币{A_1，A2，...，A_N}。总是会出现一个值为 1的硬币。 I 需要达到M的最小数量的硬币是多少？

约束条件是：

• 1≤N≤25
• 1≤米≤10^6
• 1≤A_I≤100

好的，我知道这是改变的问题。 我试图解决这个问题，使用广度优先搜索，动态编程和贪婪（这是不正确的，因为它并不总是提供最佳的解决方案）。但是，我得到超时限制（3秒）。

所以我想知道是否有这个问题的优化。 描述和约束称为我的注意，但我不知道如何使用它对我有利：

• 总是会出现值为1的硬币。
• 1≤A_I≤100

我在维基百科看到，这个问题也可以通过“与概率卷积树动态规划”来解决。但我什么都听不懂。

你能帮我吗？ 这个问题可以在这里找到：http://goo.gl/nzQJem

Answer 1

让a_n是最大的硬币。使用这两个线索：

• 结果是>= ceil(M/a_n)，
• 结果的配置有很多a_n's。

最好是尝试用最大的a_n's比检查它是否是用更少的a_n's更好的结果，直到它有可能找到更好的结果。

类似于：let R({a_1, ..., a_n}, M)是返回给定问题结果的函数。比R可以执行：

num_a_n = floor(M/a_n) 
best_r = num_a_n + R({a_1, ..., a_(n-1)}, M-a_n*num_a_n) 
while num_a_n > 0: 
    num_a_n = num_a_n - 1 
    # Check is it possible at all to get better result 
    if num_a_n + ceil(M-a_n*num_a_n/a_(n-1)) >= best_r: 
    return best_r 
    next_r = num_a_n + R({a_1, ..., a_(n-1)}, M-a_n*num_a_n) 
    if next_r < best_r: 
    best_r = next_r 
return best_r