贪心算法 2008.doc

贪心算法 2008-10-14 21:20:06| 分类： 信息技术 | 标签： |字号大中小 订阅 . 贪心算法 　 　 　 　 最优化问题是程序设计中一类非常重要的问题。 每一个最优化问题都包含一组约束条件和一个优化函数，满足约束条件的问题求解方案称为问题的可行解，使优化函数取得最优值的可行解称为问题的最优解。贪心算法是解决最优化问题的一种基本方法。 它采用逐步构造最优解的思想，在问题求解的每一个阶段，都作出一个在一定标准下看上去最优的决策；决策一旦作出，就不可再更改。制定决策的依据称为贪婪准则。 使用贪婪算法解决问题，通常需要做好以下几个方面的工作： 1、明确问题的求解目标。 2、分析问题所包含的约束条件。 3、建立优化函数。优化函数通常可以通过综合分析问题的求解目标及约束条件归纳出来。 4、制定贪婪准则。清楚问题的求解目标、所包含的约束条件及优化函数之后，就可以着手制定一个可行的贪婪准则。贪婪准则的制定是用贪婪算法解决最优化问题的关键，它关系到问题能否得到成功解决及解决质量的高低。 把以上几个方面的工作都完成了，问题自然会不攻自破。 例1：计算发放工资时所需的最少人民币张数。输入数据为职工的工资数。要求统计并输出应发给该职工面值100元、50元、20元、10元、5元、2元、1元的人民币各多少张，使总张数最少。 分析：举个具体例子，假设某职工的工资为638元，我们该发给他多少张人民币呢？答案可以是638张面值1元的人民币，可以是638/2=319张面值2元的人民币，……无论发给该职工人民币多少张，他拿到的人民币总和都应等于他自己的工资数。如果以mz[i]表示第i种人民币的面值，zs[i]表示职工拿到的第i种人民币的张数，zggz表示职工的工资数，那么应有： =zggz（根据题意，共有7种面值的人民币）。这是问题的约束条件。再阅读题目，我们发现问题的求解目标是“使总张数最少”。相应的优化函数是职工拿到的人民币张数，即 。满足约束条件 =zggz并使 取得最优值（在这里为最小值）的求解方案就是问题的最优解。 要发给该职工638元的工资，并使总张数最少，直觉告诉我们，应先给他6张面值100元的人民币；第7张不能再给100元的，也不能给50元的，否则该职工实际拿到的工资将会超过他应得的工资；显然，第7张应为面值20元的人民币。同理，第8张为面值10元的人民币，第9张为面值5元的人民币，第10张为面值2元的人民币，第11张为面值1元的人民币。该职工共拿到人民币11张，分别为面值100元的6张，面值50元的没有，面值20元、10元、5元、2元和1元的各1张。这样，不但满足了约束条件 =zggz，即100×6+（20+10+5+2+1）×1＝638，而且使该职工拿到的人民币张数最少。把以上操作方法归纳出来就是一种可行的贪婪准则：按面值从大到小的顺序分发人民币，并始终保证职工实际拿到的工资不超过他应得的工资。参考程序如下： dim mz(1 to 7) as integer dim zs(1 to 7) as integer cls : input zggz mz(1) = 100: mz(2) = 50: mz(3) = 20 mz(4) = 10: mz(5) = 5: mz(6) = 2: mz(7) = 1 for i = 1 to 7 zs(i) = 0 next i i = 1: sy = zggz rem 变量sy用来记录在给某职工发工资的过程中，某一时刻还需要付给该职工的人民币总数 do while i = 7 and sy 0 do while mz(i) * (zs(i) + 1) = sy zs(i) = zs(i) + 1 loop sy = sy - zs(i) * mz(i) i = i + 1 loop for i = 1 to 7 print mz(i); :; zs(i) next i end 例2：旅行家的预算（1999年全国青少年信息学（计算机）奥林匹克分区联赛高中组复赛试题第三题） 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离d1、汽车油箱的容量c（以升为单位），每升汽油能行驶的距离d2、出发点每升汽油的价格p和沿途油站数n（n可以为零），油站i离出发点的距离di、每升汽油的价格pi（i=1,2, ……n）。 计算结果四舍五入至小数点后两位。 如果无法到达目的地，则输出“No solution”。 分析：对于任意给定的输入数据，并不一定能保证旅行家能够到达目标城市。如果旅行家不能到达目的地，那么对最少费用的预算将毫无意义。所以，在预算最少费用之前，有必要对输入数据进行分析，看是否能使旅