It is just integer knapsack. On Fri, Jul 29, 2011 at 11:34 AM, Arun Vishwanathan <[email protected]>wrote:
> 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 <[email protected]>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 >> <[email protected]>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 [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. >>> >> >> >> >> -- >> 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 [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. > -- *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 [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.
