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 wrote:
> Thank you. But can you offer your proof?
>
> On Feb 8, 3:02 am, Dave wrote:
>
>
>
> > The greedy algorithm always gives the optimal solution if:
> > c_1 = 1, and
> > c_i
Thank you. But can you offer your proof?
On Feb 8, 3:02 am, Dave 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 wrote:
>
>
>
>
>
>
>
> > The classical coin-changing problem can be s
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 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