1、贪心法（贪婪法）2022-12-172 of 158n数钱数钱一出纳员支付一定数量的现金。假设他手一出纳员支付一定数量的现金。假设他手中有各种面值的纸币和硬币，要求他用最中有各种面值的纸币和硬币，要求他用最少的货币数支付规定的现金。少的货币数支付规定的现金。例如，现有例如，现有4种硬币：它们的面值分别为种硬币：它们的面值分别为1分、分、2分、分、5分和分和1角。要支付角。要支付2角角5分。分。首先支付首先支付2个个1角硬币，然后支付一个角硬币，然后支付一个5分分硬币，这就是贪心策略。硬币，这就是贪心策略。2022-12-173 of 158n贪心法不一定能产生正确的答案。贪心法不一定能产生正确
2、的答案。n例如，若引进一个例如，若引进一个1角角1分的硬币，设分的硬币，设从如下集合从如下集合1,1,2,2,2,5,10,10,11,11中中数出数出25分，按贪心法，共分，按贪心法，共4个硬币。个硬币。但最优解仅为但最优解仅为3个硬币。个硬币。n这说明贪心法得到的解只是一个可行这说明贪心法得到的解只是一个可行解。解。2022-12-174 of 158货郎担（TSP）问题n设售货员要到五个城市去售货，最后设售货员要到五个城市去售货，最后再回到出发的城市。已知从一个城市再回到出发的城市。已知从一个城市到其他城市的费用，求总费用最少的到其他城市的费用，求总费用最少的路线路线2022-12-17
3、5 of 158权为13从不同结点出发：从不同结点出发：1）结点）结点a为起点：为起点：2）结点）结点b为起点：为起点：3）结点）结点c为起点：为起点：4）结点）结点d为起点：为起点：权为13权为13权为13abcd213743或者152022-12-176 of 158n而实际上图中最短哈密顿而实际上图中最短哈密顿回路的长度为回路的长度为12。即即abcdaabcd2137432022-12-177 of 158Huffman编码n某通讯系统只使用某通讯系统只使用5 5种字符种字符a a、b b、c c、d d、e e，使用频率分别为使用频率分别为0.1,0.14,0.2,0.26,0.3,
4、利用二叉树设计不等长编码：利用二叉树设计不等长编码：1 1）构造以）构造以 a a、b b、c c、d d、e e为叶子的二叉树；为叶子的二叉树；2 2）将该二叉树所有左分枝标记）将该二叉树所有左分枝标记0 0，所有右，所有右 分枝标记分枝标记1 1；3 3）从根到叶子路径上标记作为叶子结点所）从根到叶子路径上标记作为叶子结点所 对应字符的编码；对应字符的编码；2022-12-178 of 158 a ac cb bd de ea:000 b:001a:000 b:001c:01 d:10c:01 d:10e:11e:115 5种字符种字符a a、b b、c c、d d、e e，使用频率分别，
5、使用频率分别为为0.1,0.14,0.2,0.26,0.330000-(1000+1400)30000-(1000+1400)*3 3-(2000+2600+3000)-(2000+2600+3000)*2 2=7600=76002022-12-179 of 158Huffman编码:贪心选择性质算法导论算法导论P234以及教材以及教材P1122022-12-1710 of 158Huffman编码:贪心选择性质2022-12-1711 of 158背包问题 已知一个容量大小为已知一个容量大小为M重量的背包和重量的背包和n种种物品，物品物品，物品i的重量为的重量为wi,假定物品假定物品i的一部
6、的一部分分xi放入背包会得到放入背包会得到vixi这么大的收益，这么大的收益，这里，这里，0 xi1，vi0。采用怎样的装包方。采用怎样的装包方法才会使装入背包的物品总效益最大？法才会使装入背包的物品总效益最大？例：考虑以下情况下的背包问题例：考虑以下情况下的背包问题n=3,M=20,(v1,v2,v3)=(25,24,15)(w1,w2,w3)=(18,15,10)2022-12-1712 of 158n=3,M=20,(v1,v2,v3)=(25,24,15)(w1,w2,w3)=(18,15,10)n1)按效益值非增次序将物品依次放入按效益值非增次序将物品依次放入背包背包 (x1,x2,
7、x3)wixi vixin2)按物品重量的非降次序将物品依次按物品重量的非降次序将物品依次放入背包放入背包(1,2/15,0)2028.2(0,2/3,1)20312022-12-1713 of 158n=3,M=20,(v1,v2,v3)=(25,24,15)(w1,w2,w3)=(18,15,10)n3)按按vi/wi的非增次序将物品依次放入的非增次序将物品依次放入背包背包 (x1,x2,x3)wixi vixi(0,1,1/2)2031.5算法：背包问题的贪心算法算法：背包问题的贪心算法2022-12-1714 of 158void GreedyKnapsack(int n,float
8、M,float v,float w,float x)Sort(n,v,w);/使使v1/w1v2/w2vn/wn for(int i=1;i=n;i+)xi=0;float c=M;for(int i=1;ic)break;xi=1;c-=wi;if(ix3(2)X=(1,1,1/2,0)Y=(1,1,1/2,1/2)j=3,k=4,所以所以kj,并且并且y4x4从而证明了从而证明了ykxk ，并且并且k0,当且当且仅当任务仅当任务i在它的期限截止以前被完成时，在它的期限截止以前被完成时，任务任务i才能获得才能获得pi的效益，每个任务的期限的效益，每个任务的期限从整个工序的开工开始计时，问应如
9、何安从整个工序的开工开始计时，问应如何安排加工顺序，才能获得最大效益？排加工顺序，才能获得最大效益？n=6,(p1,p2,p3,p4,p5,p6)=(5,25,20,30,10,15),(d1,d2,d3,d4,d5,d6)=(1,5,2,3,3,2)2022-12-1722 of 158n有限期的任务安排问题有限期的任务安排问题首先按效益非增次序进行排序，然后按照首先按效益非增次序进行排序，然后按照期限依次对此次序进行调整，排在后面的期限依次对此次序进行调整，排在后面的或提前或排除。或提前或排除。n算法的粗略描述算法的粗略描述void Greedy-Job(D,J,n)/*任务按任务按 p1
10、 p2 pn 的次序输入，它的次序输入，它们的期限值们的期限值Di 1,1in,n 1,J是可以是可以在它们的期限截止前完成的任务的集合在它们的期限截止前完成的任务的集合*/2022-12-1723 of 158 J 1;for(i=2;id(J(k),即任务即任务i的期限比的期限比这这k个任务的所有期限都长，则个任务的所有期限都长，则i可直可直接加入到接加入到k个任务的后面，即个任务的后面，即J(k+1)=in（b）将）将d(J(k),d(J(k-1),d(J(1)逐个与逐个与d(i)比较比较,直到找到位置直到找到位置q，它，它使得使得d(J(q)d(i)d(J(t)qt qtk 这说明：第
11、这说明：第t个要加工的任务以及它以后加工的个要加工的任务以及它以后加工的所有任务都可以向后移动一个单位时所有任务都可以向后移动一个单位时间。即这间。即这k-q个任务均可延迟一个单个任务均可延迟一个单位时间加工。在以上条件成立的情况位时间加工。在以上条件成立的情况下，只要下，只要 d(i)q+1，就可将任务，就可将任务i插入到第插入到第q+1个位置上，从而得到一个位置上，从而得到一个按期限的非降次序排列的含有个按期限的非降次序排列的含有k+1个任务的可行解。个任务的可行解。2022-12-1727 of 158n以上过程反复进行到对第以上过程反复进行到对第n个任务处个任务处理完毕。所得到的贪心解
12、就是一个最理完毕。所得到的贪心解就是一个最优解。优解。任务任务 0 1 2 3 4 5 6 pi 0 30 25 20 15 10 5 di 0 3 5 2 2 3 1nJ(1)=3 J(2)=4 J(3)=1 J(4)=2 总效益：总效益：902022-12-1728 of 158nvoid greedy-job(d,J,n,k)/*任务按任务按 p1 p2 pn 的次序输入，的次序输入，它们的期限值它们的期限值d(i)1,1in,n 1,J(i)是最优解中的第是最优解中的第i个任务，结束时个任务，结束时d(J(i)d(J(i+1)*/2022-12-1729 of 158n d(0)0;J
13、(0)0;k 1;J(1)1;for(i=2;i=n;i+)q k;if (d(J(q)d(i)&d(J(q)q)qq-1;if (d(J(q)d(i)&d(i)q)2022-12-1730 of 158 for(t=k;t=q+1;t-)J(t+1)J(t);J(q+1)i;k k+1;2022-12-1731 of 158活动安排:问题描述有有n个活动集个活动集E=1,2,n使用同一资使用同一资源，而同一时间内同一资源只能由一源，而同一时间内同一资源只能由一个活动使用。每个活动的使用时间为个活动使用。每个活动的使用时间为si,fi)i=1,n，si为开始时间，为开始时间，fi为为结束时间，
14、若结束时间，若si,fi)与与sj,fj)不相交不相交称活动称活动i和活动和活动j是相容的。是相容的。问题：选出最大的相容活动子集合。问题：选出最大的相容活动子集合。2022-12-1732 of 158l贪心策略贪心策略 将各活动按结束时间将各活动按结束时间排序排序f1f2fn，先选出活动，先选出活动1，然后按活动编好从小到大的次，然后按活动编好从小到大的次序依次选择与当前活动相容的活动。序依次选择与当前活动相容的活动。注：这种策略使剩余的可安排时间极大注：这种策略使剩余的可安排时间极大化，以便于安排尽可能多的相容活动。化，以便于安排尽可能多的相容活动。证明：见证明：见算法导论算法导论P22
15、42022-12-1733 of 1582022-12-1734 of 158void ActivitySelection(int n,s,f,bool a)/f已排序，已排序，a记录选择的活动，即记录选择的活动，即ai=true表示活动表示活动i已选已选择择 a1=true;int j=1;for(int i=2;i=fj)ai=true;j=i;else ai=false;T(n)=O(nlogn)2022-12-1735 of 158活动安排:计算示例11 11个活动已按结束时间排序，用贪心算法求解：个活动已按结束时间排序，用贪心算法求解：i 1 2 3 4 5 6 7 8 9 10 1
16、1start_timei 1 3 0 5 3 5 6 8 8 2 12finish_timei 4 5 6 7 8 9 10 11 12 13 1401234567891011121314time a1a2a3a4a5a6a7a8a9a10a11相容活动：相容活动：a3,a9,a11,a1,a4,a8,a11,a2,a4,a9,a1101234567891011121314timea1a2a3a4a5a6a7a8a9a10a112022-12-1736 of 158最小生成树n最小生成树的定义最小生成树的定义nKruskal算法算法 nPrim算法算法2022-12-1737 of 158网络
17、的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。2022-12-1738 of 158144187125818410909461121234212351464337139180218642704621740849867MIAPVDJFKBWIDFWLAXSFOORDBOS144187125818410909461121234212351464337139180218642704621740849867MIAPVDJFKBWIDFWLAXSFOORD
18、BOS2022-12-1739 of 158 Kruskal Kruskal最小生成树算法最小生成树算法 Kruskal 在1956年提出了1个最小生成树算法。设G=(V,E)是一个连通带权图，V=1,2,n。将图中的边按其权值由小到大排序，然后作如下的贪婪选择，由小到大顺序选取各条边，若选某边后不形成回路，则将其保留作为树的一条边；若选某边后形成回路，则将其舍弃，以后也不再考虑。如此依次进行，到选够（n-1）条边即得到最小生成树。2022-12-1740 of 158例如，对于下图中的带权图各边按权值排序为：d13=1 d46=2 d25=3 d36c4 d14=5d34=5 d23=5 d
19、12=6 d35=6 d56=62022-12-1741 of 158按Kruskal算法选取边的过程如下图所示。2022-12-1742 of 158 Kruskal Kruskal最小生成树算法最小生成树算法2022-12-1743 of 158 Prim Prim最小生成树算法最小生成树算法 Prim在1957年提出另一种算法，这种算法特别适用于边数相对较多，即比较接近于完全图的图。此算法是按逐个将顶点连通的步骤进行的，它只需采用一个顶点集合。这个集合开始时是空集，以后将已连通的顶点陆续加入到集合中去，到全部顶点都加入到集合中了，就得到所需的生成树。2022-12-1744 of 158
20、 Prim Prim最小生成树算法最小生成树算法 设G=(V,E)是一个连通带权图，V=1,2,n。构造G的一棵最小生成树的Prim算法的过程是：首先从图的任一顶点起进行，将它加入集合S中置，S=1，然后作如下的贪婪选择，从与之相关联的边中选出权值cij最小的一条作为生成树的一条边，此时满足条件iS，jV-S，并将该j加入集合中，表示连两个顶点已被所选出的边连通了。2022-12-1745 of 158 以后每次从一个端点在集合S中而另一个端点在集合S外的各条边中选取权值最小的一条作为生成树的一条边，并把其在集合外的那个顶点加入到集合S中。如此进行下去，直到全部顶点都加入到集合中S。在这个过程
21、中选取到的所有边恰好构成G的一棵最小生成树。由于Prim算法中每次选取的边两端总是一个已连通顶点和一个未连通顶点，故这个边选取后一定能将该未连通点连通而又保证不会形成回路。2022-12-1746 of 158例如，对于下图(a)中的带权图，按Prim算法选取边的过程如下图(b)所示。2022-12-1747 of 158 Prim Prim最小生成树算法最小生成树算法2022-12-1748 of 158排序之车间作业计划模型一：一台机器、一：一台机器、n个零件的排序个零件的排序目的：使得各加工零件在车间里停留的平均目的：使得各加工零件在车间里停留的平均时间最短。时间最短。零件零件加工时间加
22、工时间11.822.030.540.951.361.5若按此顺序：若按此顺序：(1.8+3.8+4.3+5.2+6.5+8)/6=4.9实际上最短：实际上最短：3,4,5,6,1,2(0.5+1.4+2.7+4.2+6+8)/6=3.82022-12-1749 of 158排序之车间作业计划模型二：两台机器、二：两台机器、n个零件的排序个零件的排序目的：使得完成全部工作的总时间最短。目的：使得完成全部工作的总时间最短。2022-12-1750 of 158某车间需要用一台车床和一台铣床加工某车间需要用一台车床和一台铣床加工A、B、C、D四四个零件。每个零件都需要先用车床加工，再用铣床加个零件。
23、每个零件都需要先用车床加工，再用铣床加工。车床与铣床加工每个零件所需的工时（包括加工工。车床与铣床加工每个零件所需的工时（包括加工前的准备时间以及加工后的处理时间）如表。前的准备时间以及加工后的处理时间）如表。工时（小时）工时（小时）ABCD车床车床8624铣床铣床31312若以若以A、B、C、D零件顺序安排加工，则共需零件顺序安排加工，则共需32小时。适当调小时。适当调整零件加工顺序，可产生不同实施方案，我们称可使所需总工整零件加工顺序，可产生不同实施方案，我们称可使所需总工时最短的方案为最优方案。在最优方案中，零件时最短的方案为最优方案。在最优方案中，零件A在车床上的在车床上的加工顺序安排
24、在第加工顺序安排在第（1）位，四个零件加工共需位，四个零件加工共需（2）小时。小时。（1）A.1 B.2 C.3 D.4（2）A.21 B.22 C.23 D.242022-12-1751 of 158以以A、B、C、D零件顺序安排加工，则共需零件顺序安排加工，则共需32小时。小时。工时（小时）工时（小时）ABCD车床车床8624铣床铣床31312车床车床A B C D862 4铣床铣床313128142032基本方法：基本方法：在第在第一一台机器上加工时间越少的零件越台机器上加工时间越少的零件越早早加工；加工；在第在第二二台机器上加工时间越少的零件越台机器上加工时间越少的零件越晚晚加工；加工
25、；2022-12-1752 of 158(1)第一个：第一个：第二个：第二个：第三个：第三个：第四个第四个:工时（小时）工时（小时）ABCD车床车床8624铣床铣床31312(2)第一个：第一个：第二个：第二个：第三个：第三个：第四个第四个:(3)第一个：第一个：第二个：第二个：第三个：第三个：第四个第四个:(4)第一个：第一个：第二个：第二个：第三个：第三个：第四个第四个:BBCBCADBCACDAB:222022-12-1753 of 158练习某车间需要用一台车床和一台铣床加工某车间需要用一台车床和一台铣床加工 A A、B B、C C、D D 四个零件。每个零件都需要先用车床加工，再用铣
26、床四个零件。每个零件都需要先用车床加工，再用铣床加工。车床和铣床加工每个零件所需的工时（包括加工。车床和铣床加工每个零件所需的工时（包括加工前的准备时间以及加工后的处理时间）如下表。加工前的准备时间以及加工后的处理时间）如下表。工时工时(小时小时)ABCD车床车床8466铣床铣床6725若以若以 A、B、C、D 零件顺序安排加工，则共需零件顺序安排加工，则共需 29 小时。小时。适当调整零件加工顺序，可产生不同实施方案，在各种适当调整零件加工顺序，可产生不同实施方案，在各种实施方案中，完成四个零件加工至少共需实施方案中，完成四个零件加工至少共需（1）小时。小时。（1）A.25 B.26 C.2
27、7 D.28 B.26 BADC 2022-12-1754 of 158解解:用网络图表示上述的工序进度表用网络图表示上述的工序进度表 网络图中的点表示一个事件网络图中的点表示一个事件,是一个或若干个工序是一个或若干个工序的开始或结束的开始或结束,是相邻工序在时间上的分界点是相邻工序在时间上的分界点,点用圆点用圆圈表示圈表示,圆圈里的数字表示点的编号。弧表示一个工圆圈里的数字表示点的编号。弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，下面标以完成此工序所需束，弧上是各工序的代号，下面标以完成此工序所需的时间（或资
28、源）等数据，即为对此弧所赋的权的时间（或资源）等数据，即为对此弧所赋的权 统筹方法统筹方法2022-12-1755 of 158统筹方法统筹方法一、计划网络图：统筹方法的第一步工作就是绘制计划一、计划网络图：统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表转换为网络图，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。统筹方法的网络图。例、某公司研制新产品的部分工序与所需时间以及它们例、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表所示，请之间的相互关系都显示在其工序进度表如表所示，请画出其统筹方法网络图。画出其统筹方法网络图。
29、工序代号工序代号工序内容工序内容所需时间（天所需时间（天)紧前工序紧前工序abcde产品设计与工艺设计产品设计与工艺设计外购配套零件外购配套零件外购生产原料外购生产原料自制主件自制主件主配可靠性试验主配可靠性试验601513388-aacb,d2022-12-1756 of 158abcde601383815工序代号工序代号工序内容工序内容所需时间（天所需时间（天)紧前工序紧前工序abcde产品设计与工艺设计产品设计与工艺设计外购配套零件外购配套零件外购生产原料外购生产原料自制主件自制主件主配可靠性试验主配可靠性试验601513388-aacb,d123452022-12-1757 of 15
30、8 将上例的工序进度表做一些扩充如下，请画出其统筹将上例的工序进度表做一些扩充如下，请画出其统筹方法的网络图。方法的网络图。工序代号工序代号 所需时间（天）所需时间（天）紧前工序紧前工序工序代号工序代号所需时间所需时间（天）（天）紧前工序紧前工序abcd60151338aacefgh810165b,dde,abcde6013838152022-12-1758 of 158工序代号工序代号 所需时间（天）所需时间（天）紧前工序紧前工序工序代号工序代号所需时间所需时间（天）（天）紧前工序紧前工序abcd60151338aacefgh810165b,dde,abcde601383815f102022
31、-12-1759 of 158 为此需要设立虚工序。虚工序是实际上并不存为此需要设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。不需要人力、物力等资源与时间。10152643a60b158e13dc38fabcde6013838152022-12-1760 of 1581256734a6015bec13d388h510fg161257834a6015bec13d388h510f616g 在绘制统筹方法的网络图时，要注意图中不能在绘制统筹方法的网络图时，要注意图中不能有缺口和回路。有缺口和回路。
32、2022-12-1761 of 158练习练习工序代号工序代号工序内容工序内容所需时间（天）所需时间（天）紧前工序紧前工序abcdefghij生产线设计生产线设计外购零配件外购零配件下料、锻件下料、锻件工装制造工装制造1木模、铸件木模、铸件机械加工机械加工1工装制造工装制造2机械加工机械加工2机械加工机械加工3装配调试装配调试60451020401830152535/aaaacdd,egb,i,f,h2022-12-1762 of 15812346785a60b45echj35ig1030d204025f18152022-12-1763 of 158二、网络时间与关键路线二、网络时间与关键路线
33、 在绘制出网络图之后，可以由网络图求出：在绘制出网络图之后，可以由网络图求出：1、完成此工程项目所需的最少时间。、完成此工程项目所需的最少时间。2、每个工序的开始时间与结束时间。、每个工序的开始时间与结束时间。3、关键路线及其应用的关键工序。、关键路线及其应用的关键工序。4、非关键工序在不影响工程的完成时间的前提下，其、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久。开始时间与结束时间可以推迟多久。2022-12-1764 of 158把工程计划表示为有向图，用顶点表示事件，弧表示活动；把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已
34、完成，在它之后的活动可以开始每个事件表示在它之前的活动已完成，在它之后的活动可以开始例例 设一个工程有设一个工程有11项活动，项活动，9个事件个事件事件事件 V1表示整个工程开始表示整个工程开始事件事件V9表示整个工程结束表示整个工程结束问题：（问题：（1）完成整项工程至少需要多少时间？）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？）哪些活动是影响工程进度的关键？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=42022-12-1765 of 158n定义定义nAOE网网(Activity On Edge)也叫边
35、表示活动的网。也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间弧表示活动，权表示活动持续时间n路径长度路径长度路径上各活动持续时间之和路径上各活动持续时间之和n关键路径关键路径路径长度最长的路径叫关键路径路径长度最长的路径叫关键路径nVe(j)表示事件表示事件Vj的最早发生时间的最早发生时间nVl(j)表示事件表示事件Vj的最迟发生时间的最迟发生时间ne(i)表示活动表示活动ai的最早开始时间的最早开始时间nl(i)表示活动表示活动ai的最迟开始时间的最迟开始时间nl(i)-e(i)表示完成活动表示
36、完成活动ai的时间余量的时间余量n关键活动关键活动关键路径上的活动叫关键活动，即关键路径上的活动叫关键活动，即l(i)=e(i)的活动的活动2022-12-1766 of 158n问题分析问题分析n如何找如何找e(i)=l(i)的关键活动？的关键活动？设活动设活动ai用弧用弧表示，其持续时间记为：表示，其持续时间记为：dut()则有：（则有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut()jkaiv如何求如何求Ve(j)和和Vl(j)？(1)从从Ve(源点源点)=0开始递推开始递推为头的弧的集合是所有以其中jTnjTjijidutiVeMaxjVei2,),()()(2)从从V
37、l(汇点汇点)=Ve(汇点汇点)开始向开始向回回递推递推为尾的弧的集合是所有以其中iSniSjijidutjVlMiniVlj11,),()()(2022-12-1767 of 158n求关键路径步骤求关键路径步骤n求求Ve(i)n求求Vl(j)n求求e(i)n求求l(i)n计算计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点顶点 Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动活动 e l le 00026
38、6465877777101616141403020230030032022-12-1768 of 158某工程包某工程包括括 A、B、C、D、E、F、G 七个作业，七个作业，各个作业的紧前作业、所需时间、所需人数如下表：各个作业的紧前作业、所需时间、所需人数如下表：作业作业ABCDEFG紧前作业紧前作业ABBC，DE所需时间所需时间（周）（周）1113232所需人数所需人数5935261该工程的计算工期为该工程的计算工期为 周。周。2022-12-1769 of 158124635A11CE2B1D3F3G2作业作业ABCDEFG紧前作业紧前作业ABBC，DE所需时间所需时间（周）（周）111
39、3232所需人数所需人数5935261答案：答案：7周周 2022-12-1770 of 158124635A11CE2B1D3F3G2V1V2V3V4V5V6顶点顶点 Ve Vl011437031457ABCDEFG活动活动 e l le02001113443513ABCDEFG1周周1132325人人9352612022-12-1771 of 158124635A11CE2B1D3F3G2ABCDEFG活动活动 e l le02001113443513ABCDEFG1周周1132325人人935261B(9)A(5)D(5)A(5)C(3)D(5)A(5)C(3)D(5)C(3)F(6)F
40、(6)F(6)2022-12-1772 of 1584.2 贪心算法的基本要素 对于一个具体的问题，怎么知对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及道是否可用贪心算法解此问题，以及能否得到问题的最优解呢能否得到问题的最优解呢?这个问题这个问题很难给予肯定的回答。很难给予肯定的回答。但是，从许多可以用贪心算法但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有求解的问题中看到这类问题一般具有2 2个重要的性质：个重要的性质：贪心选择性质和和最优子结构性质。2022-12-1773 of 1584.2 贪心算法的基本要素1.贪心选择性质 所谓所谓贪心选择性质是指所求问是指所求
41、问题的题的整体最优解可以通过一系列可以通过一系列局部最优的选择，即贪心的选择，即贪心选择来达到。这是贪心算法可行的第一个基本选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区要素，也是贪心算法与动态规划算法的主要区别。别。动态规划算法通常以动态规划算法通常以自底向上的方式解各的方式解各子问题，而贪心算法则通常以子问题，而贪心算法则通常以自顶向下的方式的方式进行，以迭代的方式作出相继的贪心选择，每进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小作一次贪心选择就将所求问题简化为规模更小的子问题。的子问题。2022-12-1774 of
42、1584.2 贪心算法的基本要素2.最优子结构性质 当一个问题的最优解包含其子当一个问题的最优解包含其子问题的最优解时，称此问题具有问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构。问题的最优子结构性质是该问题可用动态规划算法或性质是该问题可用动态规划算法或贪心算法求解的关键特征。贪心算法求解的关键特征。2022-12-1775 of 1584.2 贪心算法的基本要素3.3.贪心算法与动态规划算法的差异贪心算法与动态规划算法的差异 贪心算法和动态规划算法都要求问题具有贪心算法和动态规划算法都要求问题具有最优子结构性质，这是最优子结构性质，这是2 2类算法的一个共同点。类算法的一个共
43、同点。但是，对于具有但是，对于具有最优子结构的问题应该选用贪的问题应该选用贪心算法还是动态规划算法求解心算法还是动态规划算法求解?是否能用动态是否能用动态规划算法求解的问题也能用贪心算法求解规划算法求解的问题也能用贪心算法求解?下下面研究面研究2 2个经典的个经典的组合优化问题，并以此说明，并以此说明贪心算法与动态规划算法的主要差别。贪心算法与动态规划算法的主要差别。2022-12-1776 of 1584.2 贪心算法的基本要素n0-1背包问题：给定给定n n种物品和一个背包。物品种物品和一个背包。物品i i的重量的重量是是WiWi，其价值为，其价值为ViVi，背包的容量为，背包的容量为C
44、C。应如何。应如何选择装入背包的物品，使得装入背包中物品的选择装入背包的物品，使得装入背包中物品的总价值最大总价值最大?在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i i只有只有2 2种选择，即种选择，即装入背包或不装入背包。不能将物品装入背包或不装入背包。不能将物品i i装入背包多次，也不能只装入背包多次，也不能只装入部分的物品装入部分的物品i i。2022-12-1777 of 1584.2 贪心算法的基本要素n背包问题：与与0-10-1背包问题类似，所不同的是在选择物背包问题类似，所不同的是在选择物品品i i装入背包时，装入背包时，可以选择物品i的一部分，而，而不
45、一定要全部装入背包，不一定要全部装入背包，1in1in。这这2 2类问题都具有最优子结构性质，类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法极为相似，但背包问题可以用贪心算法求解，而求解，而0-10-1背包问题却不能用贪心算法背包问题却不能用贪心算法求解。求解。P1062022-12-1778 of 1584.2 贪心算法的基本要素用贪心算法解背包问题的基本步骤：用贪心算法解背包问题的基本步骤：首先计算每种物品单位重量的价值首先计算每种物品单位重量的价值Vi/WiVi/Wi，然后，依贪心选择策略，将尽可能多的然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将
46、这种物的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未品全部装入背包后，背包内的物品总重量未超过超过C C，则选择单位重量价值次高的物品并尽，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。去，直到背包装满为止。2022-12-1779 of 1584.2 贪心算法的基本要素 对于对于0-10-1背包问题，贪心选择之所以不能背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间证最终能将背包装满，部分闲置的背包
47、空间使每公斤背包空间的价值降低了。事实上，使每公斤背包空间的价值降低了。事实上，在考虑在考虑0-10-1背包问题时，应比较选择该物品和背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解问题。这正是该问题可用动态规划算法求解的另一重要特征。的另一重要特征。实际上也是如此，动态规划算法的确可以实际上也是如此，动态规划算法的确可以有效地解有效地解0-10-1背包问题。背包问题。2022-12-1780 of 1584.3 最优装载
48、有一批集装箱要装上一艘载重量有一批集装箱要装上一艘载重量为为c c的轮船。其中集装箱的轮船。其中集装箱i i的重量为的重量为WiWi。最优装载问题要求确定在装载体积不最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装受限制的情况下，将尽可能多的集装箱装上轮船。箱装上轮船。2022-12-1781 of 1584.3 最优装载 有一批集装箱要装上一艘载重量有一批集装箱要装上一艘载重量为为c c的轮船。其中集装箱的轮船。其中集装箱i i的重量为的重量为WiWi。最优装载问题要求确定在装载体积不最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装受限制的情况下，将尽可能多的
49、集装箱装上轮船。箱装上轮船。假设假设n=8,w1,.,w8=100,200,50,90,150,50,20,80,c=400。2022-12-1782 of 1584.3 最优装载 从剩下的货箱中，选择重量最小从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪以装载更多的货箱。根据这种贪婪策略，首先选择最轻的货箱，婪策略，首先选择最轻的货箱，然后选次轻的货箱，如此下去直然后选次轻的货箱，如此下去直到所有货箱均装上船或船上不能到所有货箱均装上船或船上不能再容纳其他任何一个货箱。再
50、容纳其他任何一个货箱。2022-12-1783 of 158w1,.,w8=100,200,50,90,150,50,20,80,c=400。利用贪婪算法时，所考察货箱的顺序为利用贪婪算法时，所考察货箱的顺序为7,3,6,8,4,1,5,2。货箱货箱7,3,6,8,4,1的总重量为的总重量为3 9 0个单位且已被装载，剩下的装载能力为个单位且已被装载，剩下的装载能力为1 0个单位，小于剩下的任何一个货箱。个单位，小于剩下的任何一个货箱。在这种贪婪解决算法中得到在这种贪婪解决算法中得到x1,.,x8 =1,0,1,1,0,1,1,1 且且xi=6。2022-12-1784 of 1584.3 最
