贪心算法解读： 1.贪心算法建议通过一系列步骤来构造问题的解，每一步都对目前构造的部分做一个扩展，直到获得问题的完整解为止。 2.在每一步中，它“贪心”地选择最佳操作，并希望通过一系列局部的最优选择，能够产生一个整个问题的全局最优解 3.事实上，贪心算法不是对所有问题都能得到整体最优解，但许多问题他能产生整体最优解或整体最优的近似解。
贪心算法举例——找零钱 买东西时，售货员常常会计算最少需要找多少张零钱，以便简化工作流程。比如顾客购物需要48.5元，他交给售货员100元整，则售货员最少需要找三张零钞：50元一张，1元一张，5角一张。
算法分析： 
贪心算法举例——石子合并问题 在操场上的四周摆放N堆石子，现要将石子有序的合并成一堆，规定每次只能选相邻的两堆合并，并将新的一堆石子记作为该次合并得分。已知每堆石子数量，请选择一种方案，使得N-1次合并得分的总和最小。 
得到总分和=8+13+22=43 得到总分和=5+9+9+15+24=62 我们来看另外一种不用贪心法 这里我们得到总分的和是=6+7+11+13+24=61 这里大家可做思考
下面来给大家运用编程举例 贪心算法——活动安排问题
1.设有n个活动的集合S=（1，2….,n），其中每个活动都要求使用同一资源，如学校礼堂，而在同一时间内只有一个活动能使用该资源。 2.每个活动都有使用的起始时间b1和结束时间e1，如果bi>=ej或bj>=ej（即一个活动结束后另一个开始）则活动i与活动j相容。 3.活动安排问题就是要在所给的活动集合中选出最大的相容活动子集。
贪心策略——选择结束时间尽量早的活动，以便腾出更多时间留给后续活动 不妨假设活动已安排好。我们来用编程实现该问题 1.在下列算法中，n为活动个数，数组b[]和e[]分别为活动开始和结束时间，假设活动已经按结束时间递增排列：e[1]<=e[2]<=…<=e[n] 2.数组A记录所有选择的活动，A[i]=1表示活动i被选中，A[i]=0表示活动i未被选中
GreedyActivitySelector(n,b[],e[],A[]) { A[1]=1; //选中活动1 j=1; //记录最后选中的活动 for(i从2到n) { if(b[i]>=e[j]){ A[i]=1; //选中活动i j=i //记录最后选中的活动 } } }免责声明：文章内容来自互联网，本站不对其真实性负责，也不承担任何法律责任，如有侵权等情况，请与本站联系删除。
转载请注明出处：程序设计与问题求解——贪心算法实例解读 https://www.yhzz.com.cn/a/13687.html