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 <[email protected]>wrote: > give explaination > > > > On Fri, Dec 16, 2011 at 11:14 AM, atul anand <[email protected]>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 <[email protected]>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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
