Question: You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount.
Answer: Let's rephrase the question like this:
"Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S."
It is simple - for each coin j, Vj≤i, look at the minimum number of coins found for the i-Vjsum (we have already found it previously). Let this number be m. If m+1 is less than the minimum number of coins already found for current sum i, then we write the new result for it.
For a better understanding let's take this example:
Given coins with values 1, 3, and 5.And the sum S is set to be 11.
First of all we mark that for state 0 (sum 0) we have found a solution with a minimum number of 0 coins. We then go to sum 1. First, we mark that we haven't yet found a solution for this one (a value of Infinity would be fine). Then we see that only coin 1 is less than or equal to the current sum. Analyzing it, we see that for sum 1-V1= 0 we have a solution with 0 coins. Because we add one coin to this solution, we'll have a solution with 1 coin for sum 1. It's the only solution yet found for this sum. We write (save) it. Then we proceed to the next state - sum 2. We again see that the only coin which is less or equal to this sum is the first coin, having a value of 1. The optimal solution found for sum (2-1) = 1 is coin 1. This coin 1 plus the first coin will sum up to 2, and thus make a sum of 2 with the help of only 2 coins.This is the best and only solution for sum 2. Now we proceed to sum 3. We now have 2 coins which are to be analyzed - first and second one, having values of 1 and 3. Let's see the first one. There exists a solution for sum 2 (3 - 1) and therefore we can construct from it a solution for sum 3 by adding the first coin to it. Because the best solution for sum 2 that we found has 2 coins, the new solution for sum 3 will have 3 coins. Now let's take the second coin with value equal to 3. The sum for which this coin needs to be added to make 3 , is 0. We know that sum 0 is made up of 0 coins. Thus we can make a sum of 3 with only one coin - 3. We see that it's better than the previous found solution for sum 3 , which was composed of 3 coins. We update it and mark it as having only 1 coin. The same we do for sum 4, and get a solution of 2 coins - 1+3. And so on.
Pseudocode:
Here are the solutions found for all sums:
Sum Min. nr. of coins Coin value added to a smaller sum to
obtain this sum (it is displayed in brackets)0 0 - 1 1 1 (0) 2 2 1 (1) 3 1 3 (0) 4 2 1 (3) 5 1 5 (0) 6 2 3 (3) 7 3 1 (6) 8 2 3 (5) 9 3 1 (8) 10 2 5 (5) 11 3 1 (10)
As a result we have found a solution of 3 coins which sum up to 11.
Additionally, by tracking data about how we got to a certain sum from a previous one, we can find what coins were used in building it. For example: to sum 11 we got by adding the coin with value 1 to a sum of 10. To sum 10 we got from 5. To sum 5 we got from 0. Thus, we find the coins used are: 1, 5 and 5.
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Hi!
First of all: Nice Blog!
Second: Nice Article.
However, there is something in your pseudocode which bothers me: what kind of condition is "Min[i-Vj]+1". I mean it can't be if this yields a non-zero value, because it will always yield a non-zero value... I'm kind of confused, because I guess that it is more or less THE line to solve whole the problem, isn't it?
Kind Regards.
Thanks Anonymous for pointing that out.
It was coz of editing problem in blogger. I have pasted a screenshot now, please re-read.
Isn't this a subset sum problem??
What is the runtime complexity of your solution? I have a solution in O(n*S) where n is the number of coins available and S the sum that needs to be obtained.
I couldn't follow your explanation. So I'm going to put forth my own here. You may want to give it a read.
Let the denomination of all the coins be available in an array C. The size of this array is obviously going to be n. In your example this array is [1, 3, 5]. S = 11. Also assume that the array is sorted in increasing order.
Let's start with the greatest denomination available. A cashier can pick 0 or 1 or 2 or 3... coins of denomination 5. So let's do that.
(i) Pick 0 coins with value=5. You now have to figure out the sum S from the rest of the array, i.e. from index 0 to the end (n-2)
(ii) Pick 1 coin with value=5. You now have to find the sum S-5 from the rest of the array, i.e. from index 0 to the end (n-2)
(iii) Pick 2 coins with value=5. You now have to find the sum S-10 from the rest of the array, i.e. from index 0 to the end (n-2)
Obviously, you can't pick 3 coins of denomination 5, because then you will exceed the sum.
The three subproblems are going to give you three results, pick the one with the minimum # of coins.
Formally, this recurrence can be stated as :
P(i, j) = min { k + P(i-1, j-k*C[i] } 0 <= k <= floor(j/C[i])
P(i, j) is the minimum # of coins required to build a sum j from the coins from index 0 to i.
The base condition is P(0, x) and can be computed as
y = 0;
if (x % C[0] == 0) {
y = x/C[0];
}
return y;
P(0, 0) = 0;
Let's run the program on S=11, C=[1, 3, 5]
P(2, 11) = min{P(1, 11), 1+P(1, 6), 2+P(1,1)}
Now calculate P(1, 11)
P(1, 11) = min{P(0, 11), 1 + P(0, 8), 2 + P(0, 5), 3 + P(0, 2)}
P(0, 11) = 11 // base condition
P(0, 8) = 8 // base condition
P(0, 5) = 5 // base condition
P(0, 2) = 2 // base condition
P(1, 11) = min{11, 9, 7, 5} = 5 // running the minimum
Calculate P(1, 6)
P(1, 6) = min{ P(0, 6), 1 + P(0, 3), 2 + P(0, 0)}
P(0, 6) = 6 // base condition
P(0, 3) = 3 // base condition
P(0, 0) = 1 // base condition
P(1, 6) = min { 6, 4, 3 } = 3 // running the minimum
P(1, 1) = min {P(0, 1)} = 1
P(2, 11) = min { 5, 4, 3 } = 3
The coins that we have chosen are 5 + 5 + 1
Anonymous
you have some mistake.in your comment your write that P(0,0)=0 and then you wrote that P(0,0)=1. which is correct?