Thank you. But can you offer your proof?
On Feb 8, 3:02 am, Dave <dave_and_da...@juno.com> wrote:
> The greedy algorithm always gives the optimal solution if:
> c_1 = 1, and
> c_i >= 2*c_{i-1}, i = 2, 3, ..., n.
>
> Dave
>
> On Feb 7, 11:35 am, ziyuang <ziyu...@gmail.com> wrote:
>
>
>
>
>
>
>
> > The classical coin-changing problem can be stated as follow:
> > Given an integer set C={c_1, c_2, ... c_n} where c_1=1 and c_i < c_{i
> > +1}, and an positive integer M,
> > find the minimum of \sum_{i=1}^n x_i, where all x_i's are non-negative
> > integers and subject to \sum_{i=1}^n x_i c_i = M
>
> > And it is well known that the problem can be solved by dynamic
> > programming. Further, in some special cases a greedy strategy also
> > works.
> > So my question is for what kind of C (the coin system) the problem
> > stated above can only be done by dp, and in what cases the other
> > method can also be adopted.
>
> > Thank you.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
