I just wanted to know if there is any efficient and optimal algorithm for the classical problem of finding the minimum number of coins that sum up to a number S where S can be very large (up to 10^16). In this case, the coins are (2, 5, 10). The DP solution is not efficient enough in this case, so I wondered if a greedy approach may work on this specific set of coins but I am not sure.
Thank you!
In order to minimize the number of coins we trivially notice that to get to 20, we need two 10-coins. (and no 2-coins nor 5-coins).
More generally to get close to 10k (with k a multiple of 10), we just need 10-coins.
Now for sums which are not multiple of 10, we may want to use a maximum of 10-coins. Say S = 10k + 2. The minimum of coins is k+1. (k 10-coins, and one 2-coin).
So the goal is to get find (k,r), such that S = 10k +r, (r < 10).
We trivially do so by usage of % operator.
r = S % 10
k = S - S % 10
Now find all combination needed for 2-coins and 5-coins for every r
2=2
4=2+2
5=5
6=2+2+2
7=5+2
8=2+2+2+2
9=5+2+2
1=5+2+2+2 (%10)
3=5+2+2+2+2 (%10)
I put 1 and 3 cases at the bottom because they are special cases.
To reach 21, we need to go up to 10, then make 11 (5+2+2+2)
Same holds for 23 we can't go to 20, we need to go to 10, then make 13 (with 5+2+2+2).
The key point being to make a sum with a combination of a 2-coins and b 5-coins such that 2a + 5b = r % 10
Finally
S%10=r not in {1, 3}, get to (S - (S%10))=10k with k 10-coins and complete(S - 10 - S%10)=10(k-1) with k-1 10-coins and completeFinal note as noticed by @Iłya Bursov we can't make it for S=1 or S=3.
All others S can be reached.