之所以再写一篇Blog，是因为现实中很多问题都可以转化成“找换硬币”问题和“0-1”背包问题。因此，需要细细理解。其次，在“参考资料”中汇总关于贪心算法与动态规划的一些Blog及学习资料。区别：其实最大的区别就是：找换硬币问题中的某类硬币是可以多次...

一，问题介绍最近一直在看贪心算法的正确性证明（如何证明贪心算法获得的解一定是最优解），感觉“剪枝”技巧用得比较多。再看了下《算法导论》中贪心算法一章里面的一个练习---找换硬币问题。这个问题对于某些面值的硬币是有最优解的，故记录下其中的一些证明思路。考虑用最少的硬币数来找n分钱的问题，假设每个硬...