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