算法设计与分析课堂讨论作业

算法设计与分析课堂讨论作业软件工程专业第一小组2011年4月26日作业1.找硬币问题组织人员分配：算法设计：杜麒麟，曹鹏程序分析：高峰，曹天亮编程：高峰，杜麒麟文档编辑：曹天亮讲解：曹鹏

问题描述：一位顾客买了价值x元的商品，并将y元钱交给收货员。币值面额种类由他人定义，怎么得到最少的找钱组合？

问题分析：此问题与课本上例3-15类似，不同之处在于，此问题能使用的找钱币值和

要找钱数是都是在程序运行时定义；例3-15中用到的币值为市面上用到的币种，为了

能达到找钱张数最少的目的，应该尽量多

地取大面额的币种，由大面额到小面额币

种逐渐进行。此方法对于本体来说已不适

用，因为我们不能确定按照此方法得出的

找钱数最少。

看例子：若找钱数为10元，能使用的币种分别为7元，5元，2元，1元。若用之前的方法求解，得到的结果为：7元，2元，1元各一张；但事实上很容易发现只需要两张5元就能找齐。

因为没有良好的算法证明哪一次得出的找钱组合为最优，所以需要将所有的方法全部遍历一遍，从中找出最优解。

此问题中，对找钱方式的探索采用的是回溯法。找钱还是由大到小进行，在找钱的过程中。若完成了一种方法的探索或者此方法走不通时，就回溯返回到上一组找钱币值，尝试用其他币值进行探索。所以数据结构可以使用堆栈进行探索，每次找到货币就进栈，找钱结束或失败时就退一次栈，用别种货币进行尝试，满足再进栈，直到将所有方式遍历一遍为止

上述方法确实能有效找到最优解但是由于找钱组合众多难免运算时间较长，所以我们可以在定义一个数组，将第一次的结果存入数组并记为临时最优解，记录找钱数（即栈中数据个数）之后在每次探索中，在进栈后比较栈的长度与数组长度，若比数组长即不可能成为最优解，按照搜索失败进行退栈，如果探索成功,且长度较短，就将栈中数据更新到数组中。这样可以跳过大部分的无用探索从而提高运算效率，这也就是我们常说到的剪枝法。存在缺陷：若找钱最少的解决方案存在多解的情况，（例如要找10元，可找钱数为3元，5元和7元就存在两种情况，两张5元或一张3元一张7元）此算法只能得出一组解（最先得到的那组）因为多解的不确定性，导致无法确定答案数组的数量，所以只存一组。对于多解问题则留到以后进行讨论。数据结构：数组moneys[]：用来存放能找的货币种类变量money：用来存放待找钱数堆栈answerStack：用来存放每次探索中货币种类在数组moneys中的标号；具有属性

length以及函数push()和pop()数组answer[]用来存放临时和最终结果；具有属性length算法：回溯法，剪枝法数据用例：用例1：找钱数10元，可用货币种类7元，5元，

2元，1元用例2:找钱数7元,可用货币种类5元,3元程序源代码：

运行程序：复杂度分析:本算法的基本思想是回溯法，但和回溯法

又有一定的区别，我们采用的是动态的解

空间——堆栈。因此，咋一看似乎有无限种可能情况。但实际上，我们可设最小的面

值为min,最大的面值为max,而要找之钱为

money,则money一定处在[min,max)这样的一个半开区间之内。算法的空间复杂度实际上就是栈的深度，因此，考虑最糟糕的情况，也即所找面值为为最小币值，那么栈的最大深度为money/min，也即可看做算法的空间复杂度为

O(money/min).算法的时间复杂度：本算法的时间耗费是在于搜索和回溯的过程，也就是栈的入栈和出栈的次数，考虑最糟糕的情况，即无解的情况，这时就会穷举大部分的组合。设币的种类为n,则组合数为

An1+An2+…+Ann

<=n*n!,也即此算法的时间复杂度的上限。但实际上，由于剪枝函数发挥的巨大作用，实际例子中的时间复杂度是远远小于理论值的。比如若moneys[