Coin Change Optimization

Question

I'm trying to solve this problem:

Suppose I have a set of n coins {a_1, a2, ..., a_n}. A coin with value 1 will always appear. What is the minimum number of coins I need to reach M?

The constraints are:

• 1 ≤ n ≤ 25
• 1 ≤ m ≤ 10^6
• 1 ≤ a_i ≤ 100

Ok, I know that it's the Change-making problem. I have tried to solve this problem using Breadth-First Search, Dynamic Programming and Greedly (which is incorrect, since it don't always give best solution). However, I get Time Limit Exceeded (3 seconds).

So I wonder if there's an optimization for this problem. The description and the constraints called my attention, but I don't know how to use it in my favour:

• A coin with value 1 will always appear.
• 1 ≤ a_i ≤ 100

I saw at wikipedia that this problem can also be solved by "Dynamic programming with the probabilistic convolution tree". But I could not understand anything.

Can you help me? This problem can be found here: http://goo.gl/nzQJem

Answer 1

Let a_n be the largest coin. Use these two clues:

• result is >= ceil(M/a_n),
• result configuration has lot of a_n's.

It is best to try with maximum of a_n's and than check if it is better result with less a_n's till it is possible to find better result.

Something like: let R({a_1, ..., a_n}, M) be function that returns result for a given problem. Than R can be implemented:

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