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.com>wrote: > >> 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] < i && memo[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.
