归本程子末军 2.4算法正确性证明 HANDONG UNIVERSITY OF TECHNOLOOY 3会会会会空会空合 定理2：设E=l,2,以是n个洁法动集合，5，/是活动i 的起始终止时同，具f3≤.可n,使A是E的活动安排 问题的一个最优解具包括活动1，则A二A-乃 是E二∈E小S之}的洁动安排闷题的最优解。 证.里赋，A'中的活动是相客的.仅需要证明A是最大的. 役不然，存在一个E'的活动姿排问题的最优解B”, B'>A. 令B=IUB'.对于M∈E,s,2∫，B中活动湘客 B是E的一个解. 由于|A=|A|+1,|B曰B1+1>A+1=A,与A最大矛盾 交理说明：活动安排问邀具有最优子结构 2025年4月3日 26
2025年4月3日 26 定理2：设E={1, 2, ., n}是n个活动集合，[si，f i ]是活动i 的起始终止时间，且f 1 f 2 .f n，设A是E的活动安排 问题的一个最优解且包括活动1，则A=A-{1} 是E={iE|si f 1 }的活动安排问题的最优解. 证.显然，A’中的活动是相容的.仅需要证明A是最大的. 设不然，存在一个E’ 的活动安排问题的最优解B’ ， B’>A’. 令B={1}∪B’. 对于iE’, si f 1 , B中活动相容. B是E的一个解. 由于|A|=|A’|+1, B=B’+1>A’+1=A，与A最大矛盾. 2.4 算法正确性证明 定理2说明：活动安排问题具有最优子结构
归本程上太军 2.4算法正确性证明 SHANDONG UNIVERSITY OF TECINOLOGY 定理3.孩E=L,2,以是n个动集合，f=0,4是 E=j∈E|S≥fn,q化最茅i长加入到放选暴合中的洁动}中 具有景小猪束对同f的洁动.税A是E的包舍洁动1的景优韩， 其中f≤.≤fn,则A= 证对A作归纳法. U 省A=1时，由定理1，命题成立 设A<k时，命题成立 省A=k时，由定理2，A=}UA1, A,是E2=j∈E|s;≥f的最优解. 由恤抽酸楼，A=心以于是，4行 家理3说明：父心选林最终可得到活动安排问题 的一个最优解
2025年4月3日 27 定理3.设 E={1, 2, ., n} 是 n 个活动集合，f0=0, li 是 Ei ={ jE | sj fq，q记录第i次加入到被选集合中的活动} 中 具有最小结束时间fl i 的活动.设A是E的包含活动1的最优解, 其中 f1 . fn，则A= 证.对A作归纳法. 当A=1时,由定理1，命题成立. 设A<k时，命题成立. 当A=k时,由定理2，A={1}∪A1 , A1是 E2 = { jE | sj f 1 } 的最优解. 由归纳假设，A1= . 于是, A= . k i i l 1 { } = k i i l 2 { } = k i i l 1 { } = 2.4 算法正确性证明 定理3说明：贪心选择最终可得到活动安排问题 的一个最优解
白东程子太军 提纲 SHANDONG UNIVERSITY OF TECINOLOGY 一、 贪心算法的基本思想 二、活动安排问题 三、最优装载 四、 哈夫曼编码 五、单源最短路径 六、最小生成树 七、多机调度问题 2025年4月3日 28
2025年4月3日 28 提纲 一、贪心算法的基本思想 二、活动安排问题 三、最优装载 四、哈夫曼编码 五、单源最短路径 六、最小生成树 七、多机调度问题
归本程上太军 3.1问题定义 SHANDONG UNIVERSITY OF TECHNOLOGY Optimal Loading problem ●有一批集装箱要装上一艘载重量为℃的轮船。其 中集装箱的重量为W。最优装载问题要求确定 在装载体积不受限制的情况下，将尽可能多的 集装箱装上轮船。 max ∑x i=1 x,∈{0,11≤i≤n) 2025年4月3日 29
2025年4月3日 29 3.1 问题定义 ⚫ Optimal Loading problem ⚫ 有一批集装箱要装上一艘载重量为c的轮船。其 中集装箱i的重量为Wi。最优装载问题要求确定 在装载体积不受限制的情况下，将尽可能多的 集装箱装上轮船。 = n i i x 1 max ( ) = x i n w x C i n i i i 0,1 1 1
归本程子末军 3.2贪心选择 SHANDONG UNIVERSITY OF TECINOLOGY ● 采用重量最轻者先装的贪心选择策略，可 产生最优装载问题的最优解。 2025年4月3日 30
2025年4月3日 30 3.2 贪心选择 ⚫采用重量最轻者先装的贪心选择策略，可 产生最优装载问题的最优解