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