Take an array of size Min[N+1][S+1]
where, N is the total no. of unique denominations and S is the total
sum
Let the value array be V[N]; // let it be 1- based indexed for ease of
explanation in the below given code snippet.
Initialize the following:
a) for (i =0; i <= N; ++i)
Min[i][0] = 0;
// this signifies that the min no. of coins that are needed to
make a value of zero is 0.
b) for (j =1; j <= S; ++i)
Min[0][j] = -1;
// this signifies that is we have used all kind of coins and
still not able to make a sum = S.
for ( int i =1; i <= S)
{
for ( int j = 1; j <= N)
{
int min1, min2;
if ( j - V[i] >= 0)
{
min1 = Min[i][j - V[i]]; // taking another instance of
the current coin..
min2 = Min[i - 1][j - V[i]]; // skipping the current
coin and looking up in V[1 ... i-1]
if ( min1 != -1 )
{
if ( min2 != -1)
M[i][j] = Min(min1, min2) + 1;
else
M[i][j] = min1 + 1;
}
else if (min2 != -1)
M[i][j] = min2 + 1;
else
Min[i][j] = -1;
}
else
Min[i][j] = -1;
}
}
Ans: Min[N][S], if Min[N][S] == -1, that means its not possible to
make the sum otherwise the positive value held by Min[N][S] will give
you the minimum no. of coins.
Basically what we are trying to do here is that, use the current
instance of the coin and see if we can get a minimum or use the
instances from the previous (i-1) coins to see if we can get a
minimum..
Time Complexity: O ( N * S) ,
Space Complexity: O(N*S)
-----------------------------
You can also solve the above problem having a space complexity of
O(S)..
All you need to do is have an array Min[S+1] where,
M[0] = 0 // basically means that using the given set of coins you were
able to make a sum of S, hence you reached M[0].
for ( i =1; i <= S; ++i)
{
M[i] = min(M[i - V[j]]) + 1 for all,
1<=j<= N and
(i - V[j]) > =0
M[i - V[j]] != -1
If we dont get a min with the above constraints then set Min[i] = -1
}
As you can see that the time complexity of the above algo is O( N* S)
Ans : Min[S] will give you the minimum no. of coins. In case its set
to -1, that means there is no such combination that can lead to S.
On Dec 16, 11:09 am, atul anand <atul.87fri...@gmail.com> wrote:
> please run algo on rough , here is the basic idea : bcoz we are allowed to
> use same coin n number of times to form the given sum.
> so for eg example given coin is 1 rs and S=10;
>
> s[10] = 1 ,after 1st iteration , this mean that we can use 1 Rs coin to
> form Rs 10 ( adding 1 Rs *10 = 10)
> hence we found 1 way.
> llly for other coins others.
>
> On Fri, Dec 16, 2011 at 11:25 AM, sangeeta goyal
> <sangeeta15...@gmail.com>wrote:
>
>
>
>
>
>
>
> > give explaination
>
> > On Fri, Dec 16, 2011 at 11:14 AM, atul anand <atul.87fri...@gmail.com>wrote:
>
> >> use dynamic programming to solve this problem :-
>
> >> here is the algo:-
>
> >> result[S];
> >> result[0]=1;
> >> index;
> >> for i=0 to len(coins[])
>
> >> c=coins[i];
>
> >> for k=c to S
> >> index=k-c;
> >> result[k]= result[k] + result[index];
>
> >> end
>
> >> end
>
> >> print result[S];
>
> >> On Fri, Dec 16, 2011 at 10:52 AM, Sangeeta <sangeeta15...@gmail.com>wrote:
>
> >>> 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.
>
> >>> 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.
>
> >>> --
> >>> You received this message because you are subscribed to the Google
> >>> Groups "Algorithm Geeks" group.
> >>> To post to this group, send email to algogeeks@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> For more options, visit this group at
> >>>http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
