第五章贪心算法 §1基本思想 找零钱假如售货员需要找给小孩67美分的零钱。现在,售货员 手中只有25美分、10美分、5美分和1美分的硬币。在小孩的催促 下,售货员想尽快将钱找给小孩。她的做法是:先找不大于67美分 的最大硬币25美分硬币,再找不大于67-25=42美分的最大硬币 25美分硬币,再找不大于42-25=17美分的最大硬币10美分硬币, 再找不大于17-10=7美分的最大硬币5美分硬币,最后售货员再找 出两个1美分的硬币。至此,售货员共找给小孩6枚硬币。售货员的 原则是拿尽可能少的硬币个数找给小孩。从另一个角度看,如果售货 员将捡出的硬币逐一放在手中,最后一起交给小孩,那么售货员想使 自己手中的钱数增加的尽量快些,所以每一次都尽可能地捡面额大的 硬币 装载问题有一艘大船用来装载货物。假设有n个货箱,它们的 体积相同,重量分别是W1,w2…wn,货船的最大载重量是c。目标 是在船上装最多货箱该怎样装?如果用x=1表示装第i个货箱,而 x=0表示不装第i个货箱,则上述问题是解优化问题:求x1,x2…, 满足 wx <c (5.1) 使得 max> x 1 贪心方法,顾名思义,是在决策中总是作出在当前看来是最好的第五章 贪心算法 §1 基本思想 找零钱 假如售货员需要找给小孩 67 美分的零钱。现在，售货员 手中只有 25 美分、10 美分、5 美分和 1 美分的硬币。在小孩的催促 下，售货员想尽快将钱找给小孩。她的做法是：先找不大于 67 美分 的最大硬币 25 美分硬币，再找不大于 67－25＝42 美分的最大硬币 25 美分硬币，再找不大于 42－25＝17 美分的最大硬币 10 美分硬币， 再找不大于 17－10＝7 美分的最大硬币 5 美分硬币，最后售货员再找 出两个 1 美分的硬币。至此，售货员共找给小孩 6 枚硬币。售货员的 原则是拿尽可能少的硬币个数找给小孩。从另一个角度看，如果售货 员将捡出的硬币逐一放在手中，最后一起交给小孩，那么售货员想使 自己手中的钱数增加的尽量快些，所以每一次都尽可能地捡面额大的 硬币。 装载问题 有一艘大船用来装载货物。假设有 n 个货箱，它们的 体积相同，重量分别是w w wn , , 1 2L ，货船的最大载重量是 c。目标 是在船上装最多货箱该怎样装？如果用 = 1 i x 表示装第 i 个货箱，而 = 0 i x 表示不装第 i 个货箱，则上述问题是解优化问题：求 x1, x2,⋅⋅⋅⋅⋅⋅， xn， 满足 x c i n i ∑ i ≤ =1 w (5.1) 使得 ∑ = n i i x 1 max (5.2) 贪心方法，顾名思义，是在决策中总是作出在当前看来是最好的