[algogeeks] efficient backtracking algorithm for the coin changing problem
Need help in designing efficient backtracking algorithm for the coin changing problem. where a1, a2, an are the set of distinct coins types, where each ai is an integer. and each type is unlimited quantity. the problem to make up the exact amount C using minimum total number of coins. use backtracking template with a bounding function.. help appreciated.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] efficient backtracking algorithm for the coin changing problem
this is dynamic programming problem. try to use dynamic programming... On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Need help in designing efficient backtracking algorithm for the coin changing problem. where a1, a2, an are the set of distinct coins types, where each ai is an integer. and each type is unlimited quantity. the problem to make up the exact amount C using minimum total number of coins. use backtracking template with a bounding function.. help appreciated.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] efficient backtracking algorithm for the coin changing problem
y u need backtracking i think it can be done with DP On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Need help in designing efficient backtracking algorithm for the coin changing problem. where a1, a2, an are the set of distinct coins types, where each ai is an integer. and each type is unlimited quantity. the problem to make up the exact amount C using minimum total number of coins. use backtracking template with a bounding function.. help appreciated.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- How soon 'not now' becomes 'never'... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] efficient backtracking algorithm for the coin changing problem
What do u mean by y u need backtracking DP needs backtracking to reconstruct the solution. -Rohit On Sat, Apr 10, 2010 at 3:27 PM, Ashish Mishra amishra@gmail.comwrote: y u need backtracking i think it can be done with DP On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Need help in designing efficient backtracking algorithm for the coin changing problem. where a1, a2, an are the set of distinct coins types, where each ai is an integer. and each type is unlimited quantity. the problem to make up the exact amount C using minimum total number of coins. use backtracking template with a bounding function.. help appreciated.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- How soon 'not now' becomes 'never'... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] efficient backtracking algorithm for the coin changing problem
here is simple way to do it..: A[1000] //1000 is maximum formadable sum can be provided.. S is set of coins that you have,K is the sum to be formed initialize the array A by larege value for(x in S): A[x]=1 for 0i1000 for 0j1000 if(i+j1000 A[i]+A[j]A[i+j] ) A[i+j]=A[i]+A[j] return A[K] On Sat, Apr 10, 2010 at 6:27 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: What do u mean by y u need backtracking DP needs backtracking to reconstruct the solution. -Rohit On Sat, Apr 10, 2010 at 3:27 PM, Ashish Mishra amishra@gmail.com wrote: y u need backtracking i think it can be done with DP On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Need help in designing efficient backtracking algorithm for the coin changing problem. where a1, a2, an are the set of distinct coins types, where each ai is an integer. and each type is unlimited quantity. the problem to make up the exact amount C using minimum total number of coins. use backtracking template with a bounding function.. help appreciated.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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. -- How soon 'not now' becomes 'never'... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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 algoge...@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. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
