大航母网站建设流程,网站开发最重要的技巧,深圳品牌网站设计公司价格,松原企业网站建设文章目录 前言一、Greedy Algorithms1.1 贪心选择性质1.2 最优子结构性质1.3 正确性证明 二、典型例题2.1 Interval Scheduling间隔调度2.2 Interval Partitioning最少间教室排课2.3 Selecting Breakpoints选择加油站停靠点2.4 硬币找零2.5 Scheduling to Minimizing Lateness2… 文章目录 前言一、Greedy Algorithms1.1 贪心选择性质1.2 最优子结构性质1.3 正确性证明 二、典型例题2.1 Interval Scheduling间隔调度2.2 Interval Partitioning最少间教室排课2.3 Selecting Breakpoints选择加油站停靠点2.4 硬币找零2.5 Scheduling to Minimizing Lateness2.6最优离线缓存2.7 其它 结束语 个人主页:风间琉璃 版权: 本文由【风间琉璃】原创、在CSDN首发、需要转载请联系博主 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦 前言
提示这里可以添加本文要记录的大概内容 预览 一、Greedy Algorithms
贪心算法是一种基于贪心策略的优化算法通过一系列的选择得到问题的解它所做出的每一个选择都是当前状态下局部最好的选择即贪心选择这种启发式的策略并不能总能获得最优解通常这种算法对于解决一些最优化问题非常有效尤其是那些可以通过局部最优解来达到全局最优解的问题。
对于一个具体的问题怎么知道是否可用贪心算法解决此问题以及能否得到问题的最优解呢
这类问题一般具有两个重要的性质贪心选择性质和最优子结构性质。
1.1 贪心选择性质
贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择即贪心选择来达到。这是贪心算法可行的第一个基本要素也是贪心算法与动态规划算法的主要区别
在动态规划中每步所做出的选择往往依赖于相关子问题的解因而只有在解出相关子问题后才能做出选择。在贪心算法中仅在当前状态下做出最好选择即局部最优选择然后再去解做出这个选择后产生的相应的子问题。
贪心算法所做出的贪心选择可以依赖于以往所做过的选择但绝不依赖于将来所做的选择也不依赖于子问题的解。正是由于这种差别动态规划算法通常以自底向上的方式解各子问题而贪心算法则通常以自顶向下的方式进行以迭代的方式做出相继的贪心选择每做出一次贪心选择就将所求同题简化为规模更小的子问题。
对于一个具体问题要确定它是否具有贪心选择性质必须证明每一步所做出的贪心选择最终导致问题的整体最优解。首先考查问题的一个整体最优解并证明可修改这个最优解使其以贪心选择开始。做出贪心选择后原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择最终可得到问题的整体最优解。其中证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。
1.2 最优子结构性质
当一个问题的最优解包含其子问题的最优解时称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。在活动安排问题中其最优子结构性质表现为若A是关于E的活动安排问题的包含活动1的一个最优解则相容活动集合A’A- {1}是关于E’{ i ∈ E i \in E i∈E; s i ≥ f 1 s_i \geq f_1 si≥f1 }的活动安排问题的一个最优解。
小结 基本思想 在每次迭代中选择当时的最佳解决方案不从整体最优考虑因此贪心算法不是对所有问题都能得到整体最优解。 局部最优 v.s.全局最优贪婪算法是在每个时刻做出局部最优选择。 在某些问题中这种策略可以导致全局最优解。 算法一般分为如下三步 分解将问题分解为若干子问题解决找出合适的贪心策略求解每一个子问题的最优解合并将局部最优解堆叠成全局最优解 优点简单、高效 缺点可能不正确/可能不是最佳
1.3 正确性证明
贪心算法最难的部分不在于问题的求解而在于正确性的证明常用的证明方法有归纳法和反证法。
归纳法证明分下面两步 证明当n 1时命题成立。 假设nm时命题成立可以推导出在nm1时命题也成立。m代表任意自然数
贪心证明一般思路
①假设贪心算法不是最优的。
②设 S 1 ( i 1 , i 2 , … , i k ) S_1 (i_1, i_2, \dots, i_k) S1(i1,i2,…,ik) 表示由贪心算法得到解 $ S_2 (j_1, j_2, \dots, j_m) $表示的是最优解。 并且设 i 1 j 1 , i 2 j 2 , … , i r j r i_1 j_1, i_2 j_2, \dots, i_r j_r i1j1,i2j2,…,irjr即 S 1 , S 2 S_1,S_2 S1,S2有最多r个相同元素的解前 r 个解在贪心解和最优解中是相同的直到某个点 r 1贪心算法选择 i r 1 i_{r1} ir1而最优解选择 j r 1 j_{r1} jr1。
③由于贪心策略是按照xxx进行选择然后比较 i r 1 i_{r1} ir1 和 j r 1 j_{r1} jr1观察解的不同可以将贪心算法选择的解 i r 1 i_{r1} ir1替换最优解 j r 1 j_{r1} jr1并解释说明这样更能满足问题要求。但这与有最多r个相同元素的解冲突这与假设贪心算法不是最优的相矛盾。因此贪心算法必须是最优的。
二、典型例题
参考
2.1 Interval Scheduling间隔调度
如下图所示每个长条方块代表一个活动总有若干个活动a、b… h横坐标是时间方块的起点和终点分别代表这个活动的起始时间和结束时间。当两个活动的活动时间没有交叉即两个方块不重叠时表示这两个活动是兼容的(compatible)。问题最终是要找到一个活动子集查找相互兼容的活动的最大子集。 本问题为尽可能多的选择活动约束条件是下一个活动的开始时间大于等于上一个活动的结束时间s[i] f[j]。使用贪心算法解决该问题可能的贪心策略如下 每次选择开始时间最早的活动(不是最优解) 证明(反证法)为了方便使用不同颜色的线条代表每个活动线条的长度就是活动所占据的时间段蓝色的线条表示已经选择的活动;红色的线条表示没有选择的活动。 如图按照该贪心策略每次选择开始时间最早的活动则应该选择蓝色的活动。很明显这不是最优解因为选择红色的活动可以选择2个活动因此此策略不可靠。 **每次选择持续时间最短的活动(**不是最优解) 证明(反证法)按照该贪心策略每次选择持续时间最短的活动如下图所示在最短时间的活动位置刚好和其他活动冲突只能选择蓝色的活动很明显持续时间最短不是最优解。 **每次选择最少的冲突活动(**不是最优解) 证明(反证法)按照该贪心策略每次选择最少的冲突活动如下图所示很明显每次选择最少的冲突活动不是最优解。 每次选择结束时间最早的活动(最优解) 贪婪算法按完成时间的递增顺序考虑活动。如果该活动与已经选择的活动不冲突则选择该活动。伪代码如下 将活动按照结束时间进行排序(归并、快速排序 O ( n l o g n ) O(n log n) O(nlogn))。集合A存放已经选择的活动j并且初始化为空。然后遍历已经排好序的活动如果该活动与集合A中的活动不冲突则将该活动加入到集合A中。
证明该贪婪算法是最优的(重点)
贪心算法求interval scheduling最优证明首先在最优解中找出最接近贪心解的最接近指r的取值最大前r个一样。最后推出r不是最大largest即推出矛盾。
证明反证法
假设贪心算法不是最优的。
设 S 1 ( i 1 , i 2 , … , i k ) S_1 (i_1, i_2, \dots, i_k) S1(i1,i2,…,ik) 表示由贪心算法选择的活动集合 $ S_2 (j_1, j_2, \dots, j_m) $表示最优解中的活动集合。 并且设 i 1 j 1 , i 2 j 2 , … , i r j r i_1 j_1, i_2 j_2, \dots, i_r j_r i1j1,i2j2,…,irjr即 S 1 , S 2 S_1,S_2 S1,S2有最多r个相同元素的解前 r 个活动在贪心解和最优解中是相同的直到某个点 r 1贪心算法选择了活动 i r 1 i_{r1} ir1而最优解选择了活动 j r 1 j_{r1} jr1。 由于贪心策略是按照最早结束时间进行选择所以 i r 1 i_{r1} ir1 的结束时间比 j r 1 j_{r1} jr1的结束时间早。因此贪心算法选择 i r 1 i_{r1} ir1 后仍然为后续活动留下了最大的可能空间这就意味着可以安排更多的活动。 如果 j r 1 j_{r1} jr1 是最优解中的活动而 i r 1 i_{r1} ir1 的结束时间比 j r 1 j_{r1} jr1 更早则可以将 j r 1 j_{r1} jr1 替换为 i r 1 i_{r1} ir1并保持后续活动不受影响。但这与有最多r个相同元素的解冲突这与假设贪心算法不是最优的相矛盾。因此贪心算法必须是最优的。 对于区间调度问题Interval Scheduling常用的解题思路是贪心算法。该问题通常涉及选择尽可能多的互不重叠的区间并且在一些应用场景下区间代表任务的开始和结束时间。贪心算法的核心思想是通过局部最优选择来构建全局最优解。
2.2 Interval Partitioning最少间教室排课
课程i从 s i s_i si开始到 f i f_i fi结束。 目标找到最少的教室数量来安排所有讲座确保没有两堂课在同一时间在同一间教室上课。 这个安排使用了 4 间教室来安排 10 堂讲座 这个安排仅使用了3间教室来安排 10 堂讲座 要解决这个问题可以使用一种贪心策略通过按时间顺序安排讲座来最小化所需的教室数量。关键是按讲座的开始时间进行排序并根据教室的占用情况安排新的讲座。伪代码如下 首先按讲座的开始时间 s i s_i si 对所有讲座进行排序。d初始化为 0表示当前教室的数量。对于每一个讲座j按顺序考虑其是否可以安排到现有的某个教室中。
如果当前讲座j可以与某个教室 k兼容即在该教室的最后一个讲座结束后开始则将讲座安排到该教室并更新该教室的结束时间。如果当前讲座与所有现有的教室都不兼容即所有教室都在当前讲座的开始时间之前被占用则分配一个新教室。将 d 加 1表示新增了一间教室并将该讲座安排到新教室中。
证明: 贪心算法在讲座安排问题中使用的教室数量是最小的即贪心算法是最优的即其他任何调度方案无法减少这个教室数量。
假设贪心算法使用了d个教室来安排所有讲座需要证明任何其他调度方案也至少需要d个教室。
假设d号教室是因为安排了讲座 j而被使用的因为讲座 j 的安排与其他 d-1个教室中的讲座都不兼容。讲座j与之前安排在其他d−1 个教室中的所有讲座都不兼容因此需要一个新的教室。
这些安排在d个教室中的讲座的结束时间都在 s j s_j sj讲座 j的开始时间之后结束。因为贪心算法按照开始时间对讲座进行了排序所有与讲座j不兼容的讲座即与 j重叠的讲座都是在时间 s j s_j sj 或之前开始的。这意味着在时间$ s_j ϵ$即 s j s_j sj 稍后时这些 d个讲座都是同时进行的。 在时间 $ s_j ϵ$处有 d 个讲座重叠表明在这个时刻必须使用至少 d个教室来安排这些讲座。如果少于 d 个教室这些重叠的讲座就会导致冲突因为两个或多个不兼容的讲座将被分配到同一个教室。
因此任何调度方案都至少需要d 个教室来避免讲座的冲突。由于贪心算法使用了d 个教室且其他任何安排方案不可能使用少于 d 个教室所以贪心算法是最优的。
2.3 Selecting Breakpoints选择加油站停靠点
从普林斯顿到帕洛阿尔托沿着固定路线进行公路旅行沿途在某些点有加油站油箱容量为 C每次加油后可以行驶的最大距离为 C。目标尽量少停靠加油站进行加油。 这是一个典型的贪心算法问题目的是在公路旅行中通过选择合适的加油站停靠点使加油次数最少。贪心算法的核心思想是每次加油时都选择可以到达的最远加油站从而最大化每次加油后的行驶距离确保尽可能减少加油次数。伪代码如下 将加油站停靠点按照距离大小从小到大进行排序集合 S 存储了已经选择的停靠点初始时只包含起点 b 0 b_0 b0变量 x 用来表示当前所处的位置初始时在起点 b 0 0 b_0 0 b00。
当当前位置 x没有到达终点 b n b_n bn时继续循环寻找下一个合适的停靠点。寻找在当前油量范围内可以到达的最远的停靠点即寻找**最大点p**使得 b p b_p bp这个停靠点在当前距离x和 x C xC xC 之间。
如果下一个停靠点的位置 b p b_p bp与当前位置 x 一样说明找不到比当前位置更远的加油站当前加油无法使车子继续行驶则返回无解。否则更新当前位置 x为选择的最远可到达的停靠点 b p b_p bp将选择的停靠点 b p b_p bp加入到集合 S中。
证明该贪心算法是最优的反证法
假设贪心算法不是最优的设 0 g 0 g 1 ⋯ g p L 0 g_0 g_1 \dots g_p L 0g0g1⋯gpL表示贪心算法选择的停靠点集合$ 0 f_0 f_1 \dots f_q L$ 表示最优解中的停靠点集合。假设贪心算法和最优解在前 r个停靠点处是相同的即 f 0 g 0 , f 1 g 1 , … , f r g r f_0 g_0, f_1 g_1, \dots, f_r g_r f0g0,f1g1,…,frgr其中 r是最大的值。 在 r1个停靠点处贪心算法选择了 g r 1 g_{r1} gr1而最优解选择了 f r 1 f_{r1} fr1。由于贪心算法的选择策略是选择当前可达范围内最远的停靠点因此根据贪心选择的规则贪心选择的停靠点 g r 1 g_{r1} gr1 必然是比最优解选择的停靠点 f r 1 f_{r1} fr1更远的即 g r 1 f r 1 g_{r1} f_{r1} gr1fr1。 如果 f r 1 f_{r1} fr1是最优解中的第r1个停靠点并且 g r 1 g_{r1} gr1停靠点比 f r 1 f_{r1} fr1停靠点更远可用将 f r 1 f_{r1} fr1替换为 g r 1 g_{r1} gr1行驶更远的距离贪心算法后续的选择仍然是可行的甚至可能更优。但这与最多有r个相同元素的解冲突这与假设贪心算法不是最优的会导致矛盾。故贪心算法必须是最优的。
2.4 硬币找零
假设货币面额为 1、5、10、25、100单位分设计一种方法以最少的硬币数量支付给顾客指定金额。
贪心策略在每次迭代中选择不超过剩余金额的最大面值硬币加入找零中直到支付完成。 按从小到大的顺序排列硬币面值准备一个空集合 S 来记录选择的硬币。每次迭代选择当前剩余金额 下可以使用的最大面值硬币ck。 如果没有适合的硬币即所有硬币面值均大于 说明无解。将选择的硬币面值从 中扣除并记录在集合 S 中。 重复上述过程直至 0。最后 S 中包含了用于支付的所有硬币。
证明贪心算法对于美国硬币系统1、5、10、25、100是最优的。
归纳法
①对于小金额 x ≤ c k x \leq c_k x≤ck贪心算法直接选择最接近x的最大硬币 c k c_k ck显然是最优的。 ②假设对于所有 x c k x c_k xck贪心算法能以最少硬币数找到最优解。 考虑任意 c k ≤ x c k 1 c_k \leq x c_{k1} ck≤xck1贪心算法会选择面值为 c k c_k ck的硬币作为第一步。如果最优解没有选择 c k c_k ck由于 c k c_k ck本身是小面值硬币的倍数例如 c k 5 , 10 , 25 c_k 5, 10, 25 ck5,10,25等,则必须用足够数量的小面值硬币 c 1 , c 2 , … , c k − 1 {c_1, c_2, \dots, c_{k-1}} c1,c2,…,ck−1来凑出至少 c k c_k ck的金额。这种方法会使用更多硬币无法优于贪心算法。因此最优解必须选择硬币 c k c_k ck此时问题简化为金额 x − c k x - c_k x−ck的找零问题。
③根据归纳假设对于金额 x − c k x - c_k x−ck贪心算法可以找到最优解。因此贪心算法在金额x上也是最优的。 表格通过列出美国硬币系统的约束条件和小面值硬币的最大组合值证明了贪心算法在每一步选择面值最大且不超过当前金额的硬币是正确且最优的。
每种硬币的限制1 分硬币最多使用 4 枚。5 分硬币和 10 分硬币的总数量最多为 2 枚。25 分硬币最多使用 3 枚。100 分硬币没有限制但只在大金额时才使用。
小面值硬币的最大组合值面值 c k c_k ck的硬币若未使用由小于 c k c_k ck 的硬币组成的金额有一个上限。例如面值小于 5 的硬币最多组合出 4 分。面值小于 10 的硬币最多组合出 9 分。面值小于 25 的硬币最多组合出 24 分。面值小于 100 的硬币最多组合出 99 分。 贪心算法在某些货币系统中可能是次优的。例如对于美国邮资面值系统1, 10, 21, 34, 70, 100, 350, 1225, 1500贪心算法并不总是能找到最优解。 目标金额140 贪心解法使用了 8 枚硬币100, 34, 1, 1, 1, 1, 1, 1。 最优解2 枚硬币70, 70 2.5 Scheduling to Minimizing Lateness
在单一资源场景下给定一组任务每个任务有如下特性 t j t_j tj处理时间。 d j d_j dj截止时间。 s j s_j sj开始时间。 f j s j t j f_j s_j t_j fjsjtj完成时间。
任务的延迟定义为 l j max ( 0 , f j − d j ) l_j \max(0, f_j - d_j) ljmax(0,fj−dj),如果任务在截止时间后完成延迟就是完成时间与截止时间的差值如果在截止时间前完成延迟为0。
目标是安排任务顺序使最大延迟 L max l j L \max l_j Lmaxlj最小化。 如上图共有 6 个任务这是按完成任务时间递增排序显然这并不是最优策略最大延迟应该为1。如下图所示 按处理时间 t j t_j tj的升序对任务排序优先完成处理时间最短的任务 按照这种贪心策略首先完成任务1然后再完成任务2延迟为1。但是如果先完成任务2再完成任务1延迟为0显然这种贪心策略不是最优的。 按松弛时间 d j − t j d_j - t_j dj−tj的升序对任务排序优先完成松弛时间最小的任务。松弛时间任务剩余的可用时间即任务完成前的可分配空闲时间。排序方式 ( d 1 − t 1 ) ≤ ( d 2 − t 2 ) ≤ ⋯ ≤ ( d n − t n ) (d_1 - t_1) \leq (d_2 - t_2) \leq \dots \leq (d_n - t_n) (d1−t1)≤(d2−t2)≤⋯≤(dn−tn)。 按照松弛时间进行排序首先完成任务2然后再去处理任务1最终延迟为11-29。但是最大延迟应为1。显然也不是最优的。按截止时间 d j d_j dj的升序对任务排序优先完成截止时间最早的任务。
使用贪心算法按任务的截止时间递增顺序调度所有任务从而最小化最大延迟。 首先按任务截止时间 d j d_j dj升序排序确保先处理截止时间较早的任务。初始化当前时间t 0遍历每个任务j分配时间区间 [ s j , f j ] [s_j, f_j] [sj,fj]
任务开始时间 s j t s_j t sjt任务完成时间 f j t t j f_j t t_j fjttj
然后更新当前时间 t t t j t t t_j tttj。最后输出所有任务的时间区间 [ s j , f j ] [s_j, f_j] [sj,fj]。
在最小化最大延迟的最优调度中任务的执行是连续的没有空闲时间即没有无意义的时间间隔。由于贪心调度严格按照截止时间顺序调度任务它自然没有逆序按照按截止时间排序 d i ≤ d j d_i \leq d_j di≤dj排序,但任务j被调度在任务i之前确保了最小化最大延迟的最优性。 引理交换两个相邻且顺序错误的任务即逆序任务会减少一个逆序的数量并且不会增加最大延迟。 假设在交换之前任务的最大延迟为l交换后为l′我们需要证明交换后最大延迟 l′不大于交换前的最大延迟l。 除了任务i和j外其他任务k的延迟不会变化 l k ′ l k 对于所有 k ≠ i , j l_k l_k \quad \text{对于所有} \, k \neq i, j lk′lk对于所有ki,j。因此交换不会影响任务k的延迟。 任务i的延迟不会增加交换后任务i可能会变得早些完成所以它的延迟 l i ′ l_i li′不会大于交换前的延迟 l i l_i li l i ′ ≤ l i l_i \leq l_i li′≤li。因此任务i的延迟不会增加。 任务j的延迟不会增加如果任务j在交换前已经延迟即 l j 0 l_j 0 lj0交换后任务j会在任务i之后完成从而延迟不会增加。 任务j在交换前完成时间为 f j f_j fj它的延迟为 l j f j − d j l_j f_j - d_j ljfj−dj。交换后任务j将在任务i完成之后开始因此其完成时间变为。此 f i ′ f_i fi′时任务j的延迟变为 l j ′ f j ′ − d j l_j f_j - d_j lj′fj′−dj。由上图知j完成时间为 f i f_i fi所以上面第二个等号成立。又按截止任务时间排序有 d i ≤ d j d_i \leq d_j di≤dj所以第三个不等号成立因此第四个也成立。 证明贪心调度S是最优的。
我们要证明贪心算法生成的调度S是最优的即它能够最小化最大延迟并且它是最少逆序的调度。
假设 S ∗ S^* S∗是一个最优调度并且具有最少的逆序。可以假设 S ∗ S^* S∗是没有空闲时间的调度。 如果 S ∗ S^* S∗没有逆序那么 S ∗ S^* S∗和贪心调度S是相同的意味着 S S ∗ S S^* SS∗这时贪心调度就是最优的。 如果 S ∗ S^* S∗有逆序假设i和j是一个相邻的逆序任务即任务j被调度在任务i之前尽管ji j我们交换i和j的顺序 交换i和j并不会增加最大延迟。交换后的延迟要么相等要么减小因为我们已经证明交换相邻逆序任务不会增加最大延迟。交换i和j会严格减少逆序的数量因为逆序数减少了 1。
如果交换i和j可以减少逆序数并且不会增加最大延迟这就与 S ∗ S^* S∗是最优调度且具有最少逆序的假设相矛盾。因为根据定义 S ∗ S^* S∗是最少逆序的调度交换i和j后得到一个逆序更少的调度S但S的最大延迟不变因此S也是一个最优调度且逆序更少。因此贪心调度S是最优的。
2.6最优离线缓存
在缓存管理中最优离线缓存问题旨在通过合理的缓存替换策略来最小化缓存未命中的次数。具体来说有以下定义和目标
缓存容量: 假设缓存能够存储k个物品。请求序列: 有一系列的物品请求表示为 d 1 , d 2 , . . . , d m d_1, d_2, ..., d_m d1,d2,...,dm。缓存命中 (Cache Hit): 如果请求的物品已经存在于缓存中则为命中。缓存未命中 (Cache Miss): 如果请求的物品不在缓存中则需要将其加载到缓存中。如果缓存已满则需要替换掉现有的某个物品。
目标是设计一个替换调度使得缓存未命中的次数最小。也就是说如何在物品请求的过程中减少需要替换的物品以最大限度地减少未命中的次数。 假设缓存容量k 2初始缓存包含物品a 和 b请求序列如下 a, b, c, b, c, a, a, b。 按照最优的替换调度最终会有 2 次缓存未命中。初始缓存: [a, b],具体调度过程如下 请求 a: 缓存命中不替换。请求 b: 缓存命中不替换。请求 c: 未命中替换一个物品a缓存为 [c, b]。请求 b: 缓存命中不替换。请求 c: 缓存命中不替换。请求 a: 未命中替换一个物品c缓存为 [a, b]。请求 a: 缓存命中不替换。 Farthest-In-Future (FF) 是一种离线缓存替换策略它的核心思想是在每次缓存未命中时选择将来最晚被请求的物品进行替换。
2.7 其它
(1背包问题给定一个背包其最大承重量为W有n个物品每个物品有以下属性重量为 w i w_i wi, 价值为 v i v_i vi。选取物品或分割物品装入背包使得背包中物品的 总价值最大化。
注意这里不是0-1 背包问题(物品只能完整装入或完全不装入)分数背包问题允许将物品按比例分割装入部分重量。
贪心策略每次选择单位价值最大的物品或物品部分直到背包装满为止。如果是0-1背包该策略可能不是最优的。
2最优装载问题假设有一艘载重量为W的轮船以及一批集装箱每个集装箱的重量为 w i w_i wi。在装载体积不受限制的情况下将尽可能多的集装箱装上轮船使得装载的集装箱的总重量不超过轮船的最大载重 W。
贪心策略按集装箱的重量从小到大排序优先选择重量较轻的集装箱装载。通过选择轻的集装箱可以装入更多集装箱并且这里只考虑W。
3哈夫曼编码
哈夫曼编码的贪心策略通过每次选择频率最小的两个节点合并确保每一步都尽可能减少编码的总长度。通过不断合并最小的节点最终得到的哈夫曼树是最优的前缀编码能够实现数据压缩的最小编码总长度。
结束语
感谢阅读吾之文章今已至此次旅程之终站 。
吾望斯文献能供尔以宝贵之信息与知识也 。
学习者之途若藏于天际之星辰吾等皆当努力熠熠生辉持续前行。
然而如若斯文献有益于尔何不以三连为礼点赞、留言、收藏 - 此等皆以证尔对作者之支持与鼓励也 。
