Re: [algogeeks] Programming Puzzle!!!!!!!
Let S be the exact amount for which minimum coins are to found. And denom[] be the array which contains different denominations. Let N be the size of the denom[] array. Algo: 1. int memo[S] 2. initialize all its elements to infinite 3.for i=1 to S for j=0 to N-1 if(denom[j] imemo[i-denom[j]] +1 memo[i]) memo[i]=memo[i-denom[j]] +1 4. return memo[S] -- 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.
Re: [algogeeks] Programming Puzzle!!!!!!!
Can you please explain the logic behind this algo in detail... On Fri, Jul 29, 2011 at 11:32 AM, ankit sambyal ankitsamb...@gmail.comwrote: Let S be the exact amount for which minimum coins are to found. And denom[] be the array which contains different denominations. Let N be the size of the denom[] array. Algo: 1. int memo[S] 2. initialize all its elements to infinite 3.for i=1 to S for j=0 to N-1 if(denom[j] imemo[i-denom[j]] +1 memo[i]) memo[i]=memo[i-denom[j]] +1 4. return memo[S] -- 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. -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- 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.
Re: [algogeeks] Programming Puzzle!!!!!!!
I have used dynamic programing to solve the problem. I have used memo[] array to memoize the value of previous state. You should take an example and try to work it out using the algo... -- 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.
Re: [algogeeks] Programming Puzzle!!!!!!!
what do you mean when u say initialize all its elements to infinite. i am not able to get this logic. memo[i-denom[j]] +1 memo[i] can you please explain??? On Fri, Jul 29, 2011 at 11:32 AM, ankit sambyal ankitsamb...@gmail.comwrote: Let S be the exact amount for which minimum coins are to found. And denom[] be the array which contains different denominations. Let N be the size of the denom[] array. Algo: 1. int memo[S] 2. initialize all its elements to infinite 3.for i=1 to S for j=0 to N-1 if(denom[j] imemo[i-denom[j]] +1 memo[i]) memo[i]=memo[i-denom[j]] +1 4. return memo[S] -- 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. -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- 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.
Re: [algogeeks] Programming Puzzle!!!!!!!
It means a very large value, can be the max value that an integer can hold -- 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.
Re: [algogeeks] Programming Puzzle!!!!!!!
what do u mean by memo[i]=memo[i-denom[j]] +1 memo[i] will be containing infinite value. memo[i-denom[j]] will also contain infinite value On Fri, Jul 29, 2011 at 11:32 AM, ankit sambyal ankitsamb...@gmail.comwrote: Let S be the exact amount for which minimum coins are to found. And denom[] be the array which contains different denominations. Let N be the size of the denom[] array. Algo: 1. int memo[S] 2. initialize all its elements to infinite 3.for i=1 to S for j=0 to N-1 if(denom[j] imemo[i-denom[j]] +1 memo[i]) memo[i]=memo[i-denom[j]] +1 4. return memo[S] -- 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. -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- 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.
Re: [algogeeks] Programming Puzzle!!!!!!!
I can tell u the logic if the minimum existing coin denomination is 1 cent for instance.If the minimum denomination is not 1 u might need to modify the algorithm I guess let v1,v2.vn be the values of the coin denominations u have in the array dynamic programming solution would be as follows: we need another array to store all possible values using these coins that is say S[i] is the value i that is obtained using minimum number of coins so initialisation is S[0]=0; S[1]=1( if minimum denomination is 1 in given array) every other value S[i]= min( S[i-1] + 1, 1 if either of v1 to vn equals i) check and see if it is ok... arun On Fri, Jul 29, 2011 at 10:59 AM, AMAN AGARWAL mnnit.a...@gmail.com wrote: what do u mean by memo[i]=memo[i-denom[j]] +1 memo[i] will be containing infinite value. memo[i-denom[j]] will also contain infinite value On Fri, Jul 29, 2011 at 11:32 AM, ankit sambyal ankitsamb...@gmail.comwrote: Let S be the exact amount for which minimum coins are to found. And denom[] be the array which contains different denominations. Let N be the size of the denom[] array. Algo: 1. int memo[S] 2. initialize all its elements to infinite 3.for i=1 to S for j=0 to N-1 if(denom[j] imemo[i-denom[j]] +1 memo[i]) memo[i]=memo[i-denom[j]] +1 4. return memo[S] -- 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. -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- 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.
Re: [algogeeks] Programming Puzzle!!!!!!!
It is just integer knapsack. On Fri, Jul 29, 2011 at 11:34 AM, Arun Vishwanathan aaron.nar...@gmail.comwrote: I can tell u the logic if the minimum existing coin denomination is 1 cent for instance.If the minimum denomination is not 1 u might need to modify the algorithm I guess let v1,v2.vn be the values of the coin denominations u have in the array dynamic programming solution would be as follows: we need another array to store all possible values using these coins that is say S[i] is the value i that is obtained using minimum number of coins so initialisation is S[0]=0; S[1]=1( if minimum denomination is 1 in given array) every other value S[i]= min( S[i-1] + 1, 1 if either of v1 to vn equals i) check and see if it is ok... arun On Fri, Jul 29, 2011 at 10:59 AM, AMAN AGARWAL mnnit.a...@gmail.comwrote: what do u mean by memo[i]=memo[i-denom[j]] +1 memo[i] will be containing infinite value. memo[i-denom[j]] will also contain infinite value On Fri, Jul 29, 2011 at 11:32 AM, ankit sambyal ankitsamb...@gmail.comwrote: Let S be the exact amount for which minimum coins are to found. And denom[] be the array which contains different denominations. Let N be the size of the denom[] array. Algo: 1. int memo[S] 2. initialize all its elements to infinite 3.for i=1 to S for j=0 to N-1 if(denom[j] imemo[i-denom[j]] +1 memo[i]) memo[i]=memo[i-denom[j]] +1 4. return memo[S] -- 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. -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- 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. -- *With Regards :* Ravinder Kumar B.Tech Final Year Computer Science and Engineering MNNIT Allahabad -- 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.
Re: [algogeeks] Programming Puzzle!!!!!!!
@aman: My mistake. set* memo[0]=0* The revised algo is : Algo: 1. int memo[S] 2. initialize all its elements to infinite. * 3.memo[0]=0* 4.for i=1 to S for j=0 to N-1 if(denom[j] imemo[i-denom[j]] +1 memo[i]) memo[i]=memo[i-denom[j]] +1 5. return memo[S] -- 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.
Re: [algogeeks] Programming Puzzle!!!!!!!
isn't it knapsack problem ? On Fri, Jul 29, 2011 at 4:29 PM, ankit sambyal ankitsamb...@gmail.comwrote: @aman: My mistake. set* memo[0]=0* The revised algo is : Algo: 1. int memo[S] 2. initialize all its elements to infinite. * 3.memo[0]=0* 4.for i=1 to S for j=0 to N-1 if(denom[j] imemo[i-denom[j]] +1 memo[i]) memo[i]=memo[i-denom[j]] +1 5. return memo[S] -- 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. -- Ankur Khurana Computer Science Netaji Subhas Institute Of Technology Delhi. -- 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.
[algogeeks] Programming Puzzle!!!!!!!
Please tell me the solution of this puzzle.. 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. What is the method called -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- 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.
