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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
