|
贪心算法在对问题求解时，总是做出在当前看来是最好的选择。它所做出的是在某种意义上的局部最优解，而不保证是整体最优解。 我们先看一个贪心算法的经典例子。 第五套人民币共有1元、5元、10元、20元、50元、100元6种面额的纸币。尽管现在差不多都是移动支付了，但是现在我们要用人民币纸币来支付购买价值为V元的物品，请问最少需要多少张纸币？ 例如： 输入: V = 70 输出: 2张 需要一张50元和一张20元的纸币 算法分析 算法很简单：尽量选用面额最大的纸币，把币值进行累加，直到累加的值正好等于V。 也就是尽可能多地选择100元的纸币；然后剩余部分尽可能选择50元的纸币；之后剩余部分尽可能选择20元的纸币，…，以此类推，直到最后的剩余部分用1元的纸币。 在算法中，“尽量选用面额最大的纸币”就是在计算过程中遵循的规则，我们只考虑“尽可能多地使用面额大纸币”这个一种当前最优策略，也就是“贪心算法”的含义。 下面是算法描述： 1)向量s用于存放选择的纸币面值，初始值为空 2)找到小于或等于V的最大的面值d 3)把面值加大向量s中，同时从V中减去面值d 4)如果V变成0，输出向量s中保存的选择纸币面值，结束； 否则重复步骤2）和步骤3） 代码实现 下面是代码实现部分，你能回答其中的问题吗？ 答案：因为数组deno中纸币面额是从小到大排列，要先检查大面额的纸币 问题升级 上面的问题中，对于每种纸币的张数是没有限制的。 现在假设1元、5元、10元、20元、50元、100元6种面额的纸币分别是C1、C2、C3、C4、C5、C6，那么最少需要多少张纸币才能支付V元？（为简单起见，加上至少存在一种方案）。 我们需要增加一个数组C来存放各种面值的纸币张数。想想看如何在下面的流程图圆圈处修改使它能处理上述问题？ 答案如下： 代码如下：
|
|
|
