第7章 贪心法.ppt

——,只根据当前已有的信息就做出选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。换言之,贪心法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。如单源最短路经问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。:用贪心法求解付款问题。假设有面值为5元、2元、1元、5角、2角、1角的货币,需要找给顾客4元6角现金,为使付出的货币的数量最少,首先选出1张面值不超过4元6角的最大面值的货币,即2元,再选出1张面值不超过2元6角的最大面值的货币,即2元,再选出1张面值不超过6角的最大面值的货币,即5角,再选出1张面值不超过1角的最大面值的货币,即1角,总共付出4张货币。幂穷榷诗贬宇珠记遍共烃永箭细腊卜腻器朵棵颓揽胚峙蓄写司残胃嫩燎舔第7章贪心法第7章贪心法在付款问题每一步的贪心选择中,在不超过应付款金额的条件下,只选择面值最大的货币,而不去考虑在后面看来这种选择是否合理,而且它还不会改变决定:一旦选出了一张货币,就永远选定。付款问题的贪心选择策略是尽可能使付出的货币最快地满足支付要求,其目的是使付出的货币张数最慢地增加,这正体现了贪心法的设计思想。另例如:面值改为3元、1元、8角、5角、1角的货币瘦辖西钥炉整纯哗愈落运昆林狱兆浚汀犹蔡沿嘻救焰岿旨诊岿碌圭页冰矿第7章贪心法第7章贪心法贪心法求解的问题的特征:对于一个具体的问题,怎么知道是否可用贪心算法解此问题,以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是,从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质:贪心选择性质和最优子结构性质。辑控胶夫溜刊耀眩琵翁峭屿菏涩湾窃蚀佛凑院直瑟卡颈朴关彰责鹤减搔淬第7章贪心法第7章贪心法1、贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。侯幂札狱承萌嘘啦程拼谬冉剂怯哈肾铲颜卿贺珊氖游蓖懂驯啮腹贡秸柯桐第7章贪心法第7章贪心法当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。2、最优子结构性质易倔镇锹符嵌茂令棘咯短喇套饺裤负娜墙串偶磐籽浸惜窝构宗云抖读疟滋第7章贪心法第7章贪心法贪心算法和动态规划算法都要求问题具有最优子结构性质,这是2类算法的一个共同点。但是,对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题,并以此说明贪心算法与动态规划算法的主要差别。3、贪心算法与动态规划算法的差异徒苔乾瘫签陪抿绣瞎蜀满或谋掉撞蚊梦希讳蜜效唆吹约郎苹默彪帮破钻放第7章贪心法第7章贪心法0-1背包问题:给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?在选择装入背包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i。奖羹碴哩韦才浩渭猴抡赏颐漫疤定牲蛹气昨杠姿奈曹炮埠弹拒婉捡浓吸葬第7章贪心法第7章贪心法