@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 Bombay
http://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>
> .
> 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.
