Take a look at this paper: http://arxiv.org/PS_cache/arxiv/pdf/0809/0809.0400v1.pdf
Dave On Feb 7, 1:51 pm, ziyuang <ziyu...@gmail.com> wrote: > 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.- 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 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.