Hi anand, could you please enlighten on the running time of the code? On Sun, Jun 20, 2010 at 1:12 AM, Anand <anandut2...@gmail.com> 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 < > chakri...@gmail.com> 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 <rohit.kumar.sa...@gmail.com >> > 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 <dave_and_da...@juno.com> 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 <rohit.kumar.sa...@gmail.com> 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 <dave_and_da...@juno.com> >>>> 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 <rohit.kumar.sa...@gmail.com> >>>> 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 algoge...@googlegroups.com. >>>> > > To unsubscribe from this group, send email to >>>> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>> <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 algoge...@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%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<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> 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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%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<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 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.
