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