I need to find the number of coins that make a given value where coins are in decimals and there is a possibility that the algorithm will return more coins (money) because there is no way to return the exact value where the returned amount is close to the given value.
For example:
Coins: [23, 29.90, 34.50]
Value: 100
Possible solutions:
Solution 1: 34.60, 34.50, 29.90, 23 (122)
Solution 2: 29.90, 29.90, 29.90 ,29.90 (119.90)
Solution 3: 23, 23, 23, 23, 23 (115)
Solution 4: 23, 23, 23, 34.50 (103.5)
Based on the possible solutions, the clear winner is "Solution 4" and I am looking for an algorithm that will help me to solve this issue. I don't care how many coins are used I just need to be sure that returned values in coins are as close as passed/desired value.
Does someone know the solution or algorithm for this case?
Greedy algorithm assumes that you get the largest possible coin, then the next possible and so on until you reach the sum. But it does not provide the best solution in general case.
So consider using of table containing possible sums:
Multiply sum and all nominals by 100 to work in integers.
Make array A[] of length 1 + sum + largest_coin, filled with zeros, set A[0] into -1.
For every coin nominal C walk through array. If A[i-C] is not zero, put value C into A[i]
After all scan array range A[sum]..A[max] to find the first non-zero item. It's index K represents the best sum. This cell contains the last coin added - so you can unwind the whole combination, walking down until index 0: A[k] => A[k - A[k]] an so on
Python code
def makesum(lst, summ):
mx = max(lst)
A = [-1] + [0]*(mx+summ)
for c in lst:
for i in range(c, summ + c + 1):
if A[i - c]:
A[i] = c
print(A)
#look for the smallest possible combination >= summ
for k in range(summ, summ + mx + 1):
if A[k]:
break
if (k == summ + mx + 1):
return
# unwind combination of used coins
while (k > 0):
print(A[k])
k = k - A[k]
makesum([7, 13, 21], 30)
Array for reference. Non-zero entries - for possible sums.
[-1, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 13, 7, 0, 0, 0, 0, 0, 13, 21, 0, 0,
0, 0, 13, 13, 21, 0, 0, 0, 0, 13, 21, 21, 0, 0, 0, 13, 13, 21, 21, 0, 0, 0,
0, 21, 21, 21, 0, 0]
Combination:
13
13
7