换硬币算法贪心非最优

反例

denominations: 1, 10, 21, 34, 70, 100, 350, 1225, 1500.

Greedy: 100, 34, 1, 1, 1, 1, 1, 1.
Optimal: 70, 70.

贪心算法对换硬币 1,5,10,25,100是最优的

对于ck <= x < ck+1, 贪心算法拿走了k.
如果最优的算法没有拿走k, 那么它可以使用[1, k-1]的凑成x。

分析下：
共有1分的, 5分的, 10分的, 25分的
1分的: <= 4
5分的: <= 1
25分的: <= 3
5分的+10分的 <= 2