有时候，去便利店买几块钱的东西，但没有零钱，只能给他们一张100的，他们可能找给我一沓10块的和几枚硬币。我不喜欢这么多的零钱，要知道，钱越零散，散失地就越快，我希望找给我的零钱张数最少。
如何找出最少数目（钱的张数）的零钱呢？这个问题看起来很简单，假设要用50、20、10、5、1（元）找出87元来，任何人都可以简单地得出：1张50、1张20、1张10、1张5和2张1元就可以满足。可以用代码表示出来：
public static int[] MakeChange(int money, int[] changes)
{
int[] result = new int[changes.Length];
for (int i = 0; i < changes.Length; i++)
{
result[i] = money / changes[i];
money = money % changes[i];
if (money == 0) { break; }
}
return result;
}输入money=87，changes={ 50, 20, 10, 5, 1 }，则结果为：{ 1, 1, 1, 1, 2 }。这种方法的特点是：从最大额的零钱开始，逐次凑出需要的数额来，不关心总的数目是否真的是最小。这样的算法也形象地称为“贪心算法”，而找出最少数目的零钱的问题称为“最优化问题”。在某些情况下，贪心算法未必能得到最优的解，比如恰好10元和5元没有了，只剩下50、20和1元，这时要找出60元，需要1张50和10张1元，而实际上只要3张20就可以了。如果各种零钱是充足的，则可以证明贪心算法得到的解也是最优解。
零钱的集合是 { 50, 20, 10, 5, 1 }，记为C。对于一个特定的数额n，它的最优解记为q。那么q中至多有2个20，因为如果有3个的话，可以用1张50和1张10来代替3张20；如果有2张20，则不能有10元的，否则可以用1张50来代替，同理最多有1张5和4张1，这样可以确定如果有2张20，则在q中小于50的零钱总数在40和49之间；同理如果只有1张20的，则最多有1张10、1张5和4张1，总数在20和39之间；如果没有20，则最多有1张10、1张5和4张1，总数在0和19之间。总之，在最优解中，小于50的零钱总数在0到49之间【结论1】。有了这个结论，下面来证明上述问题中，贪心算法得到的解也是最优解。
还是使用上面的标记：零钱集合C，数额n，最优解q，假设贪心算法得到的解是q’。用q50表示q中50元的个数，q’50表示q’中50元的个数，由于q’中包含尽可能多的50，所以q50
如果各种零钱充足，现在是没问题了，如果某些零钱没有了，贪心算法未必能得到最优解，这时该如何求解呢？为简化问题，我们假设1元的钱总是充足的，所以解总是存在的。对于数额n，可做如下考虑：
1）如果n = 1，则用1个1元来找零，这就是最优解；
酷纬企业网站管理系统Kuwebs是酷纬信息开发的为企业网站提供解决方案而开发的营销型网站系统。在线留言模块、常见问题模块、友情链接模块。前台采用DIV+CSS，遵循SEO标准。 1.支持中文、英文两种版本，后台可以在不同的环境下编辑中英文。 3.程序和界面分离，提供通用的PHP标准语法字段供前台调用，可以为不同的页面设置不同的风格。 5.支持google地图生成、自定义标题、自定义关键词、自定义描
2）如果n > 1，则对于每个可能的值i，分别找出i元和n-i元来。
通过这样的递归，可以找出所有可能的解来，这样就可以找到最优解来了。不过该方法效率不高，因为存在大量冗余的计算，比如要找出60元，中间需要计算59，要计算59则一定需要计算58。。。而且这些计算要重复多次，这种情形称为“递归爆炸”。这里很像使用递归来求解Fibonacci数列一样，存在很大的效率问题。在优化Fibonacci数列的计算时，一种方法是将计算过的值存放在一个数组里，以供重复使用，这里也可以采用这样的思路。
public static void MakeChangeDynamically(int money, int[] changes, int[] changesUsed, int[] lastChange)
{
changesUsed[0] = 0;
lastChange[0] = 1;
for (int dollars = 1; dollars <= money; dollars++)
{
// 至少可以全部使用1元来找零
int minChangeCount = dollars;
int newChange = 1;
for (int j = 0; j < changes.Length; j++)
{
if (changes[j] > dollars)
{
continue; // 不能使用该数额来找零
}
// 如果使用这个数额来找所需要的数目更小
if (changesUsed[dollars - changes[j]] + 1 < minChangeCount)
{
minChangeCount = changesUsed[dollars - changes[j]] + 1;
newChange = changes[j];
}
}
changesUsed[dollars] = minChangeCount;
lastChange[dollars] = newChange;
}
}这个方法属于动态规划的应用。假设现在要找的数额为67，changes = { 1, 5, 10, 20, 50 }，changesUsed数组会保存从1到66之间的数值分别需要多少张零钱，在求解67的时候，会这样考虑：对于changes的每个数值，将67拆分为1+66，5+62，10+57，20+47，50+17，由于66、62、57、47、17这些值都已计算过，所以可以迅速得出对于67找零需要几张零钱；同时lastChange数组保存了从1到66之间的数值的最优解中，它们所使用的最后一张零钱是什么，这样回推过去，不但可以知道用几张零钱，还可以知道这些零钱的数额分别是什么。
虽然如此，在日常生活中找零钱的时候，两种方法都不需要，心算即可:)
