O(S +n ) only when the denominations are in sorted order.isn't it? On Sun, Jun 20, 2010 at 8:41 AM, Anand <[email protected]> wrote:
> Complexity will be O(S+n) S = Sum required N = Number of denominations > > On Sat, Jun 19, 2010 at 12:48 PM, Chakravarthi Muppalla < > [email protected]> wrote: > >> Hi anand, >> could you please enlighten on the running time of the code? >> >> >> On Sun, Jun 20, 2010 at 1:12 AM, Anand <[email protected]> wrote: >> >>> Here is my approach for solving this problem using DP. >>> >>> http://codepad.org/Op41weg5 >>> >>> <http://codepad.org/Op41weg5> >>> >>> On Thu, Jun 17, 2010 at 6:33 AM, Chakravarthi Muppalla < >>> [email protected]> wrote: >>> >>>> I think that we need to go by dynamic programming. >>>> Ex: 1,3,7,4,9 T=23 >>>> Sort: 1,3,4,7,9 >>>> subtract max value from T(23-9=14 ) >>>> find Best Solution for (14) --> sub (14-9 = 5), Search for 5.(5-4 = 1) >>>> So Answer would be: 9,9,4,1 >>>> Search can be binary search as the array is already sorted. >>>> At every step best solution for the specified number could be saved in a >>>> hash table for any further references. >>>> >>>> >>>> Thanks & Regards, >>>> Chakravarthi. >>>> >>>> >>>> >>>> >>>> >>>> On Thu, Jun 17, 2010 at 6:10 PM, Rohit Saraf < >>>> [email protected]> wrote: >>>> >>>>> Yes right, i forgot the "1" >>>>> >>>>> -------------------------------------------------- >>>>> Rohit Saraf >>>>> Second Year Undergraduate, >>>>> Dept. of Computer Science and Engineering >>>>> IIT Bombay >>>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>> >>>>> >>>>> On Thu, Jun 17, 2010 at 6:05 PM, Dave <[email protected]> wrote: >>>>> >>>>>> No. The greedy algorithm also works on the U.S. coinage system, where >>>>>> the coins are 1, 5, 10, 25. Again, the rule is that there must be a 1 >>>>>> unit coin, and each coin has at least twice the value of the >>>>>> preceeding one. >>>>>> >>>>>> Dave >>>>>> >>>>>> On Jun 16, 11:34 pm, Rohit Saraf <[email protected]> wrote: >>>>>> > @Dave: The greedy will only work if the coins are k,2k,3k,4k,.... nk >>>>>> without >>>>>> > any of these missing >>>>>> > Clear? >>>>>> > (Perhaps i did not write it clearly as i was on mobile) >>>>>> > -------------------------------------------------- >>>>>> > Rohit Saraf >>>>>> > Second Year Undergraduate, >>>>>> > Dept. of Computer Science and Engineering >>>>>> > IIT >>>>>> > Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>>> > >>>>>> > >>>>>> > >>>>>> > On Thu, Jun 17, 2010 at 10:00 AM, Dave <[email protected]> >>>>>> wrote: >>>>>> > > The greedy algorithm doesn't work, e.g., when the coins are 1, 5, >>>>>> and >>>>>> > > 8 units, and you want to make 15 units. In this case, the greedy >>>>>> > > algorithm would choose 8, 5, 1, 1, whereas the optimal is 5, 5, 5. >>>>>> I >>>>>> > > believe the criterion for the greedy algorithm are that the >>>>>> smallest >>>>>> > > coin be 1 unit and each successive coin be at least twice the >>>>>> value of >>>>>> > > its predecessor. >>>>>> > >>>>>> > > Dave >>>>>> > >>>>>> > > On Jun 16, 9:19 pm, Rohit Saraf <[email protected]> >>>>>> wrote: >>>>>> > > > If the coins are all multiple of some number k, you can greedily >>>>>> give >>>>>> > > > as much as possible to the higher domination. Otherwise still, >>>>>> there >>>>>> > > > is an optimal substructure and u can make a recurrence and use >>>>>> > > > memoization(i.e. DP) >>>>>> > >>>>>> > > > -- >>>>>> > > > -------------------------------------------------- >>>>>> > > > Rohit Saraf >>>>>> > > > Second Year Undergraduate, >>>>>> > > > Dept. of Computer Science and Engineering >>>>>> > > > IIT >>>>>> > > > Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>>> > >>>>>> > > -- >>>>>> > > 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]<algogeeks%[email protected]> >>>>>> <algogeeks%2bunsubscr...@googlegroups.com> >>>>>> > > . >>>>>> > > For more options, visit this group at >>>>>> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text >>>>>> - >>>>>> > >>>>>> > - Show quoted text - >>>>>> >>>>>> -- >>>>>> 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]<algogeeks%[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]<algogeeks%[email protected]> >>>>> . >>>>> For more options, visit this group at >>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>> >>>> >>>> >>>> >>>> -- >>>> Thanks, >>>> Chakravarthi. >>>> >>>> -- >>>> 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]<algogeeks%[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]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Thanks, >> Chakravarthi. >> >> -- >> 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]<algogeeks%[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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Thanks, Chakravarthi. -- 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.
