[数学]152贪心算法ppt课件

1、C+程序设计程序设计贪婪算法贪婪算法崔崔 斌斌2 53什么是贪婪法什么是贪婪法n找硬币的例子找硬币的例子n假设有四种硬币，面值分别为二角五分、一角假设有四种硬币，面值分别为二角五分、一角、五分和一分。如今要找给顾客六角三分钱。、五分和一分。如今要找给顾客六角三分钱。n如何使找给顾客的硬币数最少？如何使找给顾客的硬币数最少？n方案：方案：2个二角五分，个二角五分，1个一角和个一角和3个一分。个一分。n背后的想法：每次都首先选择面值最大的硬币背后的想法：每次都首先选择面值最大的硬币，假设剩余钱不够再选择面值次大的硬币，假设剩余钱不够再选择面值次大的硬币n-贪婪法的思想贪婪法的思想3 53背包问题：

2、背包问题：给定给定n种物品和一个背包，设种物品和一个背包，设Wi为物体为物体i的分量，的分量，Vi为期价值，为期价值，C为背包的承分量。要求在背包为背包的承分量。要求在背包的承分量的限制下，进能够使背包中物品的的承分量的限制下，进能够使背包中物品的价值最大。价值最大。贪婪战略一：每次选择价值最大的物品。贪婪战略一：每次选择价值最大的物品。贪婪战略二：每次选择分量最小的物品。贪婪战略二：每次选择分量最小的物品。贪婪战略三：每次选择贪婪战略三：每次选择Vi/Wi最大的物品最大的物品4 53n什么是贪婪法？什么是贪婪法？n“鼠目寸光的方法？每次选择面值最大的硬币鼠目寸光的方法？每次选择面值最大的硬币

3、还是能得到正确结果的还是能得到正确结果的n贪婪法在求解问题时，每一步选择的都是当前看贪婪法在求解问题时，每一步选择的都是当前看来最好的选择来最好的选择;贪婪法的关键是决议每一步该怎贪婪法的关键是决议每一步该怎样做。每次都试图选择面值最大的硬币样做。每次都试图选择面值最大的硬币n经过一系列小的步骤构成一个解，在每一步根据经过一系列小的步骤构成一个解，在每一步根据部分情况作出最优战略，构成问题的最优解把每部分情况作出最优战略，构成问题的最优解把每一步选择的最大面值的硬币交给客户就是硬币总一步选择的最大面值的硬币交给客户就是硬币总个数最少的方案个数最少的方案5 53一：事件序列问题一：事件序列问题问

4、题的描画问题的描画知知N = 12个事件的开场时辰和终了时辰，一些个事件的开场时辰和终了时辰，一些在时间上没有重叠的事件可以构成一个事件在时间上没有重叠的事件可以构成一个事件序列，事件序列包含的事件数目称为事件序序列，事件序列包含的事件数目称为事件序列的长度。列的长度。要求找出一个最长的事件序列。要求找出一个最长的事件序列。6 53贪婪战略一：每一步选择最早开场事件？贪婪战略一：每一步选择最早开场事件？7 53贪婪战略二：每一步选择最短事件？贪婪战略二：每一步选择最短事件？8 539 53把一切的事件按终了时间由小到大排序，每一把一切的事件按终了时间由小到大排序，每一步选择终了时间最早的事件，

5、并且和所选事步选择终了时间最早的事件，并且和所选事件不重叠件不重叠不重叠不重叠: a事件的终了时辰小于等于事件的终了时辰小于等于b 事件的开事件的开场时辰场时辰enda = beginb 这时这时a事件和事件和b事件不重叠，即为事件不重叠，即为a = 上一个事件终了的时间上一个事件终了的时间上一个事件终了的时间上一个事件终了的时间 = endi-1begini start_time; selecti = 1; start_time = endi；11 53#include #include using namespace std;using namespace std;const int N

6、= 12;const int N = 12;void OutputResult(int select, int N) /void OutputResult(int select, int N) /输出结果函数输出结果函数 for(int i = 0; i N; i+) for(int i = 0; i N; i+) if(selecti = 1) / if(selecti = 1) /当标志为当标志为1 1时该事件被选中时该事件被选中 cout i endl; cout i endl; 12 53int main()int main() int beginN = 1, 3, 0, 3, 2,

7、5, 6, 4, 10, 8, 15, 15; / int beginN = 1, 3, 0, 3, 2, 5, 6, 4, 10, 8, 15, 15; /开场时间开场时间 int endN = 3, 4, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20; / int endN = 3, 4, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20; /终了时间终了时间 int selectN = 0; / int selectN = 0; /标志选取哪些事件标志选取哪些事件 int i = 0; / int i = 0; /当前最早终了的事件当前最早

8、终了的事件 int time_start = 0; / int time_start = 0; /当前情况下可选事件的最早开场事件当前情况下可选事件的最早开场事件 while(i N) / while(i = time_start) / if(begini = time_start) /时间不重叠时间不重叠 selecti = 1; / selecti = 1; /选择事件选择事件i i time_start = endi; / time_start = endi; /更新后面事件的最早开场时间更新后面事件的最早开场时间 i+; i+; OutputResult(select, N); / O

9、utputResult(select, N); /输出被选择事件输出被选择事件 return 0; return 0; 13 53小结小结 1贪婪法的解题步骤贪婪法的解题步骤从问题的某个初始条件出发从问题的某个初始条件出发事件序列初始为空，第一步选择第一个事件；事件序列初始为空，第一步选择第一个事件；采用循环语句，当可以向求解目的前进一步时，采用循环语句，当可以向求解目的前进一步时，就根据部分最优战略，得到一个部分解，减少就根据部分最优战略，得到一个部分解，减少问题的范围或规模问题的范围或规模选择最早终了的事件；选择最早终了的事件；将一切的部分解综合起来，得到问题的最终解将一切的部分解综合起来

10、，得到问题的最终解每一步的最早终了事件构成最终的事件序列；每一步的最早终了事件构成最终的事件序列；14 53二：区间覆盖问题二：区间覆盖问题问题的描画问题的描画用整数用整数i来表示来表示x轴上坐标为轴上坐标为i - 1, i的区间的区间(长度长度为为1)。给出。给出M(1 = M = 200)个不同的整数，个不同的整数，表示表示M个这样的区间。个这样的区间。要求画出几条线段覆盖住一切的区间，条件是：要求画出几条线段覆盖住一切的区间，条件是：每条线段可以恣意长，但是要求所画线段的每条线段可以恣意长，但是要求所画线段的长度之和最小，并且线段的数目不超越长度之和最小，并且线段的数目不超越N(1= N

11、 = 50)。例如：给出例如：给出3个整数个整数2， 4， 6，就表示，就表示1, 2,3, 4, 5, 6这三个区间。这三个区间。15 53例如：给出例如：给出M = 5个整数个整数1，3，4，8，11表示表示区间，要求所用线段不超越区间，要求所用线段不超越N = 3条，可以有多种条，可以有多种覆盖方案。覆盖方案。8 88 87 711116 616 53贪婪战略：每次断开最长间隔贪婪战略：每次断开最长间隔17 53程序流程图程序流程图18 53数据构造：数据构造：positionm - 1，表示有，表示有m个线段个线段 poisitonk = i，表示线段，表示线段i - 1, i 表示每

12、两个线段间隔的数组表示每两个线段间隔的数组distancem-1 distancei = positioni + 1 - positioni - 1; 先求举间隔，再排序先求举间隔，再排序19 53假设曾经对区间间隔排序了，那么：假设曾经对区间间隔排序了，那么：distance0最大，最大，distance1其次。其次。开场总长度：开场总长度：nTotalLength =positionM-1 - position0 + 1每断开一次，总长度减少每断开一次，总长度减少distanceinTotalLength = nTotalLength - distancei i+, 下一次要断开的序号。下

13、一次要断开的序号。 循环多少次？循环多少次？ while(nLine 0)20 53int main()int main() const int M = 5; const int M = 5; const int N = 3; const int N = 3; int position = 1, 3, 4, 8, 11; / int position = 1, 3, 4, 8, 11; /表示线段表示线段0,1, 2, 3, 3,40,1, 2, 3, 3,4 int distanceM-1; / int distanceM-1; /线段之间的间隔线段之间的间隔 for(int i = 0;

14、i M - 1; i+) / for(int i = 0; i = M) /N if(N = M) /N大于等于大于等于MM的情况的情况 cout The total length is cout The total length is： M endl; M endl; return 0; return 0; 21 53 /N /N小于小于MM的情况的情况 int nLine = 1; / int nLine = 1; /当前运用的线段数当前运用的线段数 int nTotalLength = positionM-1 - position0 + 1;/ int nTotalLength = po

15、sitionM-1 - position0 + 1;/运用的线段长度运用的线段长度 int nDivide = 0; / int nDivide = 0; /指向当前未断开的最大间隔的间隔指向当前未断开的最大间隔的间隔 while(nLine 0) while(nLine 0) nLine+; / nLine+; /多运用一条线段多运用一条线段 nTotalLength -= distancenDivide; / nTotalLength -= distancenDivide; /断开当前最大的间隔断开当前最大的间隔 nDivide+; / nDivide+; /指向下一个最大间隔指向下一个最

16、大间隔 cout The total length is: nTotalLength endl; cout The total length is: nTotalLength endl; return 0; return 0; 22 53/ /从大到小排序从大到小排序void Sort(int value , int number)void Sort(int value , int number) for(int i = 0; i number; i+) for(int i = 0; i number; i+) for(int j = 0; j number - 1 - i; j+) for(

17、int j = 0; j number - 1 - i; j+) if(valuej valuej + 1) if(valuej = end1的活动的活动的一个最优的一个最优解。解。n一个最优解是一个最优解是0#，1#， 5#， 8#， 10# n1#， 5#， 8#， 10# 是一个最优解是一个最优解25 53最优子构造最优子构造用用n-1根线段的覆盖问题是用根线段的覆盖问题是用n根线段的覆盖问根线段的覆盖问题的一个子问题。并且题的一个子问题。并且n-1根线段覆盖的最优根线段覆盖的最优解断开下一个最大间隔后就是用解断开下一个最大间隔后就是用n根线段覆盖根线段覆盖的一个最优解。的一个最优解。当

18、遇到的问题有最优子构造的性质时，可以思当遇到的问题有最优子构造的性质时，可以思索运用贪婪法解题。索运用贪婪法解题。26 53三：最小生成树问题三：最小生成树问题电路系统电路系统思索有很多个电子组件的电路系统，为了使得思索有很多个电子组件的电路系统，为了使得组件组件i和组件和组件j的电势一样，需求把的电势一样，需求把i和和j用导线用导线相连。如何相互衔接组件，使他们之间的电相连。如何相互衔接组件，使他们之间的电势都相等，并且用最短的导线长度势都相等，并且用最短的导线长度?27 53通讯系统通讯系统思索通讯公司，如中国挪动、电信，需求构建思索通讯公司，如中国挪动、电信，需求构建一通讯网络，衔接一通

19、讯网络，衔接n个不同的用户，把用户个不同的用户，把用户i和用户和用户j连在一同的代价是连在一同的代价是ci,j。使一切用户。使一切用户相互衔接的最小费用是多少？相互衔接的最小费用是多少？28 53根本概念根本概念图：包含顶点和衔接顶点的边，假设边没有方向称图：包含顶点和衔接顶点的边，假设边没有方向称为无向图，假设边有方向称为有向图。边带有值为无向图，假设边有方向称为有向图。边带有值的图称为带权图。的图称为带权图。树：连通无回路树：连通无回路(没有圈没有圈)的无向图，的无向图，性质：性质：|E| = |V| - 1，E是边的集合，是边的集合，V是顶点集合是顶点集合29 53图的表示方法图的表示方

20、法30 53n问题的描画问题的描画n设设G = (V, E)是一个无向连通带权图，边的大是一个无向连通带权图，边的大小可以了解为边的长度。假设小可以了解为边的长度。假设G是一棵包含是一棵包含G的一切顶点的树，且树的边也是的一切顶点的树，且树的边也是G中的边，中的边，那么称那么称G为为G的生成树，生成树各边长度的的生成树，生成树各边长度的和称为该生成树的耗费。在和称为该生成树的耗费。在G的生成树中，的生成树中，耗费最小的生成树称为耗费最小的生成树称为G的最小生成树。的最小生成树。n设计算法求图的最小生成树。设计算法求图的最小生成树。31 53生成树例如生成树例如用什么方法使生成树的边的长度之和最

21、小呢，用什么方法使生成树的边的长度之和最小呢，即求最小生成树？即求最小生成树？32 53战略之一：战略之一：Prim算法算法初始形状：恣意选择一个顶点，放入集合初始形状：恣意选择一个顶点，放入集合S中；中；步骤：从图的顶点集合步骤：从图的顶点集合V - S中选择一个顶点中选择一个顶点j，顶点顶点j到集合到集合S中某个顶点中某个顶点i的边的边(i, j)的长度是的长度是一切边中最小的，把该顶点参与集合一切边中最小的，把该顶点参与集合S中；中； 终了形状：终了形状：S = V。33 53Prim算法流程图算法流程图34 53int c66 = 0, 4, INT_MAX, 5, INT_MAX,

22、INT_MAX, 4, 0, 1, INT_MAX, INT_MAX, INT_MAX, INT_MAX, 1, 0, 2, 6, INT_MAX, 5, INT_MAX, 2, 0, INT_MAX, 7, INT_MAX, INT_MAX, 6, INT_MAX, 0, 3, INT_MAX, INT_MAX, INT_MAX, 7, 3, 0;35 53nS 0 lowest costnS 0，1 lowest costnS 0，1，2 lowest costnS 0，1，2，3 lowest costnS 0，1，2，3，4 lowest costnS 0，1，2，3，4，50 4 5

23、 0 4 5 0 0 0 0 0 30 0 0 0 0 30 0 1 5 0 0 1 5 0 0 0 0 6 7 0 0 0 0 6 7 0 0 0 2 6 0 0 0 2 6 选择节点选择节点1 136 53Prim算法实现算法实现int sN表示集合表示集合S，1表示曾经参与，否那么表示曾经参与，否那么0，初始初始S0 = 1;lowcostN记录每一个顶点到集合记录每一个顶点到集合s的最短边长的最短边长度度,初始初始lowcost0, ., N-1 = c00, ., N-1lowcostN =0,4,INT_MAX, 5, INT_MAX, INT_MAX,37 53把一个节点从把一个

24、节点从V V中放到中放到S S中中int min = INT_MAX; /int min = INT_MAX; /可以表示的最大整数范围可以表示的最大整数范围int j; /int j; /用来记录下一个参与用来记录下一个参与s s的顶点的顶点for(int k = 1; k N; k+) /for(int k = 1; k N; k+) /查找最短的边查找最短的边 if (lowcostk min & (!sk) if (lowcostk min & (!sk) min = lowcostk; min = lowcostk; j = k; j = k; /j /j就是要参与的

25、顶点的编号就是要参与的顶点的编号38 53closestN记录每一个顶点到集合记录每一个顶点到集合s的最短边在集合的最短边在集合s中的顶点，初始值：中的顶点，初始值：closesti = 0假设边假设边(j, i)是是j到集合到集合s的最短的一条边，那么集合的最短的一条边，那么集合S中的点是中的点是i， 既既closestj = i，边的长度用，边的长度用lowcostj表示表示假设参与假设参与1，closest1 = 0;由于由于1到到0的边最短。同的边最短。同理：理：closest2 = 1; closest3=2；closest4 = 2; closest5=4S 0 , S 0, 1

26、, S 0, 1, 2 .S 0 , S 0, 1 , S 0, 1, 2 .39 53/ /修正集合外的顶点到集合修正集合外的顶点到集合S S里的顶点最短边的长度里的顶点最短边的长度，即更新，即更新lowcostlowcost。由于每参与一点，其他点到集合。由于每参与一点，其他点到集合里面点的边长都会发生变化。里面点的边长都会发生变化。j j是新参与的节点是新参与的节点for(int k = 1; k N; k+)for(int k = 1; k N; k+) if(cjk lowcostk) & (!sk) if(cjk lowcostk) & (!sk) lowcostk

27、 = cjk; lowcostk = cjk; closestk = j; /closest closestk = j; /closest代表一个顶点代表一个顶点 40 53#include #include #include #include using namespace std;using namespace std;const int N = 6;const int N = 6;int c66 = /int c66 = /存储图存储图 0, 4, INT_MAX, 5, INT_MAX, INT_MAX, 0, 4, INT_MAX, 5, INT_MAX, INT_MAX, 4, 0

28、, 1, INT_MAX, INT_MAX, INT_MAX, 4, 0, 1, INT_MAX, INT_MAX, INT_MAX, INT_MAX, 1, 0, 2, 6, INT_MAX, INT_MAX, 1, 0, 2, 6, INT_MAX, 5, INT_MAX, 2, 0, INT_MAX, 7, 5, INT_MAX, 2, 0, INT_MAX, 7, INT_MAX, INT_MAX, 6, INT_MAX, 0, 3, INT_MAX, INT_MAX, 6, INT_MAX, 0, 3, INT_MAX, INT_MAX, INT_MAX, 7, 3, 0, INT_

29、MAX, INT_MAX, INT_MAX, 7, 3, 0,; ;int main()int main() Prim(); Prim(); return 0; return 0; 41 53void Prim()void Prim() int lowcostN; / int lowcostN; /记录每一个顶点到集合记录每一个顶点到集合s s的最短边长度的最短边长度 int closestN; / int closestN; /记录每一个顶点到集合记录每一个顶点到集合s s的最短边的最短边 / /在集合在集合s s中的顶点中的顶点 int sN; / int sN; /集合集合s s，记录曾

30、经参与的顶点，记录曾经参与的顶点，1 1表示该表示该 / /顶点曾经参与顶点曾经参与s s s0 = 1; / s0 = 1; /初始化，首先参与号顶点初始化，首先参与号顶点 for(int i = 1; i N; i+) / for(int i = 1; i N; i+) /更新其它顶点到集合更新其它顶点到集合s s的间隔的间隔 lowcosti = c0i; /i lowcosti = c0i; /i到到s s的最短边的长度的最短边的长度 closesti = 0; /i closesti = 0; /i到到s s的最短边的另外一个顶点的最短边的另外一个顶点 si = 0; si = 0;

31、 42 53 / /还需求参与还需求参与N - 1N - 1个顶点，每一步都是贪婪选择个顶点，每一步都是贪婪选择 i = 1; i = 1; while(i N) while(i N) int min = INT_MAX; int min = INT_MAX; int j int j，k; /k; /用来记录下一个参与用来记录下一个参与s s的顶点的顶点 for(k = 1; k N; k+) / for(k = 1; k N; k+) /查找最短的边查找最短的边 if(lowcostk min & (!sk) if(lowcostk min & (!sk) min = low

32、costk; j = k; min = lowcostk; j = k; cout Node j :( j ,“ closestj ) = lowcostj endl; cout Node j :( j ,“ closestj ) = lowcostj endl; sj = 1; / sj = 1; /把把j j参与到参与到s s中中 for(k = 1; k N; k+) / for(k = 1; k N; k+) /修正剩余顶点到集合修正剩余顶点到集合s s的顶点最短边的长度的顶点最短边的长度 if(cjk lowcostk) & (!sk) if(cjk lowcostk) &a

33、mp; (!sk) lowcostk = cjk; closestk = j; lowcostk = cjk; closestk = j; i+; i+; 43 53战略之二：战略之二：Kruskal算法算法初始形状：一切顶点孤立，没有边；初始形状：一切顶点孤立，没有边； 步骤：按边的长度由小到大陈列，不断插入一条步骤：按边的长度由小到大陈列，不断插入一条边，只需不构成回路，就把边插入；假设构成边，只需不构成回路，就把边插入；假设构成回路，那么放弃这条边，选择下一个最小边；回路，那么放弃这条边，选择下一个最小边；终了形状：插入边的数目到达了终了形状：插入边的数目到达了|V| - 1。44 53

34、Kruskal算法流程图算法流程图45 53贪婪的性质贪婪的性质每个阶段面临的问题都是原问题的一个子问题每个阶段面临的问题都是原问题的一个子问题子问题的处理只与当前阶段和以后阶段的决策子问题的处理只与当前阶段和以后阶段的决策有关有关与以前各阶段的决策无关与以前各阶段的决策无关46 53贪婪算法的缺乏贪婪算法的缺乏贪婪法的留意点贪婪法的留意点-贪婪法不是万能的贪婪法不是万能的假设找硬币的例子：硬币的面值有：一分、五假设找硬币的例子：硬币的面值有：一分、五分、八分、一角，假设要找给客户的钱是一分、八分、一角，假设要找给客户的钱是一角三分。角三分。运用贪婪法的方案是：运用贪婪法的方案是：1个一角和个

35、一角和3个一分个一分而最优的方案是：而最优的方案是：1个八分和个八分和1个个5分分所以运用贪婪法时需求留意最终得到的是不是所以运用贪婪法时需求留意最终得到的是不是问题的最优解问题的最优解47 53启发式算法和次优解启发式算法和次优解贪婪法是一种不追求最优解，只希望得到较为称心解的方法。贪婪法是一种不追求最优解，只希望得到较为称心解的方法。例如找硬币问题，不思索找零钱的一切各种发表方案，而是从例如找硬币问题，不思索找零钱的一切各种发表方案，而是从最大面值的币种开场，按递减的顺序思索各币种，先尽量用最大面值的币种开场，按递减的顺序思索各币种，先尽量用大面值的币种，当缺乏大面值币种的金额时才去思索下

36、一种大面值的币种，当缺乏大面值币种的金额时才去思索下一种较小面值的币种。较小面值的币种。这种方法并不是总是最优。如只需面值分别为这种方法并不是总是最优。如只需面值分别为1、5和和11单位的单位的硬币，而希望找回总额为硬币，而希望找回总额为15单位的硬币。按贪新算法，应找单位的硬币。按贪新算法，应找1个个11单位面值的硬币和单位面值的硬币和4个个1单位面值的硬币，共找回单位面值的硬币，共找回5个硬个硬币。但最优的解应是币。但最优的解应是3个个5单位面值的硬币单位面值的硬币贪婪法普通可以快速得到称心的解，由于它省去了为找最优解贪婪法普通可以快速得到称心的解，由于它省去了为找最优解要穷尽一切能够而必

37、需耗费的大量时间。要穷尽一切能够而必需耗费的大量时间。贪婪法常以当前情况为根底作最优选择，而不思索各种能够的贪婪法常以当前情况为根底作最优选择，而不思索各种能够的整体情况，所以不要回溯。整体情况，所以不要回溯。48 53n问题描画问题描画n设有编号为设有编号为0、1、n-1的的n种物品，体积分别为种物品，体积分别为v0、v1、vn-1。将这。将这n种物品装到容量都为种物品装到容量都为V的假设干箱子里。商的假设干箱子里。商定这定这n种物品的体积均不超越种物品的体积均不超越V，即对于，即对于0in，有，有0viV。不同的装箱方案所需求的箱子数目能够不同。装箱问题要。不同的装箱方案所需求的箱子数目能

38、够不同。装箱问题要求使装尽这求使装尽这n种物品的箱子数要少。种物品的箱子数要少。n假设调查将假设调查将n种物品的集合分划成种物品的集合分划成n个或小于个或小于n个物品的一切个物品的一切子集，最优解就可以找到。但一切能够划分的总数太大。对子集，最优解就可以找到。但一切能够划分的总数太大。对适当大的适当大的n，找出一切能够的划分要破费的时间是无法接受的，找出一切能够的划分要破费的时间是无法接受的。为此，对装箱问题采用非常简单的近似算法，即贪婪法。为此，对装箱问题采用非常简单的近似算法，即贪婪法。装箱问题装箱问题49 53n不失普通性，设不失普通性，设n件物品的体积是按从大到小排好序的，即有件物品的

39、体积是按从大到小排好序的，即有v0v1vn-1。如不满足上述要求，只需先对这。如不满足上述要求，只需先对这n件物品按它件物品按它们的体积从大到小排序，然后按排序结果对物品重新编号即可们的体积从大到小排序，然后按排序结果对物品重新编号即可。装箱算法简单描画如下：。装箱算法简单描画如下：n输入箱子的容积输入箱子的容积V；输入物种类数；输入物种类数n；输入各物品的体积，排序；输入各物品的体积，排序预置已用箱子链为空；预置已用箱子链为空； 预置已用箱子计数器预置已用箱子计数器box_count为为0；for (i = 0; i n; i+)for (i = 0; i n; i+) 从第一只箱子开场顺序寻觅能放入