下载文档原格式
贪心算法的基本原理贪心算法（Greedy Algorithm）是一种常用的算法思想，它在求解最优化问题时通常能够得到较好的近似解。
贪心算法的基本原理是：每一步都选择当前状态下的最优解，从而希望最终能够得到全局最优解。
在实际应用中，贪心算法常常用于解决一些最优化问题，如最小生成树、最短路径、任务调度等。
一、贪心算法的特点贪心算法具有以下特点：1. 简单：贪心算法通常比较简单，易于实现和理解。
2. 高效：贪心算法的时间复杂度通常较低，能够在较短的时间内得到结果。
3. 局部最优：每一步都选择当前状态下的最优解，但不能保证最终能够得到全局最优解。
4. 适用范围：贪心算法适用于一些特定类型的问题，如无后效性、最优子结构等。
二、贪心算法的基本原理贪心算法的基本原理可以概括为以下几个步骤：1. 初始状态：确定问题的初始状态，定义问题的输入和输出。
2. 状态转移：根据当前状态，选择局部最优解，并更新状态。
3. 筛选解：判断当前状态下是否满足问题的约束条件，若满足则保留该解，否则舍弃。
4. 终止条件：重复以上步骤，直至满足终止条件，得到最终解。
三、贪心算法的应用举例1. 找零钱：假设有 25、10、5、1 四种面额的硬币，需要找零 41 元，如何使得找零的硬币数量最少？贪心算法可以先选择面额最大的硬币，然后逐步选择面额较小的硬币，直至找零完毕。
2. 区间调度：给定一组区间，如何选择最多的互不重叠的区间？贪心算法可以先按照区间的结束时间排序，然后依次选择结束时间最早的区间，直至所有区间都被覆盖。
3. 最小生成树：在一个连通的带权无向图中，如何选择边使得生成树的权值最小？贪心算法可以按照边的权值从小到大排序，然后依次选择权值最小且不构成环的边，直至所有顶点都被连接。
四、贪心算法的优缺点1. 优点：贪心算法简单高效，适用于一些特定类型的问题，能够在较短的时间内得到近似最优解。
2. 缺点：贪心算法不能保证一定能够得到全局最优解，可能会出现局部最优解不是全局最优解的情况。
贪心算法程序设计贪心算法程序设计1. 什么是贪心算法贪心算法（Greedy Algorithm）是一种常见的算法思想，它在每一步选择中都采取当前状态下的最优选择，从而希望最终达到全局最优解。
贪心算法的核心思想是局部最优解能导致全局最优解。
2. 贪心算法的基本步骤贪心算法的基本步骤如下：1. 定义问题的优化目标。
2. 将问题分解成子问题。
3. 选择当前最优的子问题解，将子问题的解合并成原问题的解。
4. 检查是否达到了问题的优化目标，如果没有达到，则回到第二步，继续寻找下一个最优子问题解。
5. 在所有子问题解合并成原问题解后，得到问题的最优解。
3. 贪心算法的应用场景贪心算法的应用非常广泛，几乎可以用于解决各种优化问题。
以下几个常见的应用场景：1. 零钱找零问题：给定一定面额的纸币和硬币，如何找零使得所需纸币和硬币的数量最小？2. 区间调度问题：给定一些活动的开始时间和结束时间，如何安排活动使得可以办理的活动数量最大？3. 背包问题：给定一些具有重量和价值的物品，如何选择物品使得背包的总价值最大？4. 最小树问题：给定一个带权无向图，如何找到一棵树，使得它的边权之和最小？5. 哈夫曼编码问题：给定一组字符和相应的频率，如何构造一个满足最低编码长度限制的二进制编码？4. 贪心算法的优缺点贪心算法的优点是简单、高效，可以快速得到一个近似最优解。
而且对于一些问题，贪心算法能够得到全局最优解。
贪心算法的缺点在于它不一定能够得到全局最优解，因为在每一步只考虑局部最优解，无法回溯到之前的选择。
5. 贪心算法的程序设计在使用贪心算法进行程序设计时，通常需要以下几个步骤：1. 定义问题的优化目标。
2. 将问题分解成子问题，并设计子问题的解决方案。
3. 设计贪心选择策略，选择局部最优解。
4. 设计贪心算法的递推或迭代公式。
5. 判断贪心算法是否能够得到全局最优解。
6. 编写程序实现贪心算法。
6.贪心算法是一种常见的算法思想，它在每一步选择中都采取当前状态下的最优选择，从而希望最终达到全局最优解。
贪心算法求解最优解问题贪心算法是计算机科学领域中常用的一种算法。
它常常被用来求解最优解问题，如背包问题、最小生成树问题、最短路径问题等。
贪心算法解决最优解问题的基本思路是，每一步都选取当前状态下最优的解决方案，直到达到全局最优解。
在这篇文章中，我们将为大家深入探讨贪心算法求解最优解问题的基本思路、算法复杂度和应用场景等方面的知识。
基本思路贪心算法是一种基于贪心策略的算法。
其核心思想是，每一步都采用当前最优策略，以期最终达到全局最优解。
在贪心算法中，每个子问题的最优解一般都是由上一个子问题的最优解推导出来的。
因此，关键在于如何找到最优解。
具体而言，贪心算法一般由三部分组成，分别为：状态、选择和判断。
首先，需要明确当前问题的状态，即问题的规模和限制条件。
然后，在当前的限制条件下，我们需要从可能的方案中选择出最优的方案，并把这个选择作为解的一部分。
最后，需要判断选择是否符合问题的限制条件，是否达到全局最优解。
算法复杂度在进行算法分析时，我们需要考虑算法的时间复杂度和空间复杂度。
对于贪心算法而言，其时间复杂度一般是 O(nlogn) 或 O(n) 级别的，其中 n 表示问题的规模。
这种效率在实际应用中表现出了很高的稳定性和效率。
应用场景贪心算法通常应用于需要求解最优解问题的场景中。
例如：- 贪心算法可以用来求解背包问题。
在背包问题中，我们需要在限定的空间内选取最有价值的物品装入背包中以努力获得最大的收益。
在贪心策略下，我们只需要按单位重量价值从大到小的顺序进行选择，就可以得到最优解；- 贪心算法也可以用来求解最小生成树问题。
这个问题是指，在给定一个图的时候，我们需要选出一棵生成树，使得生成树上的所有边权之和最小。
在此问题中，我们可以将图上的边权按大小排序，然后顺序选择边直至生成树。
这样，我们可以得到与全局最优解很接近的解；- 贪心算法还可以用来求解最短路径问题。
在最短路径问题中，我们需要找到从一个节点到另一个节点的最短路径。
贪心算法的概念和适用条件什么是贪心算法？贪心算法（Greedy Algorithm）是一种以局部最优解为导向的算法思想，通过每一步选择当前状态下的最佳操作来达到整体最优解的目标。
贪心算法的核心思想是每次都做出当前看来最优的选择，以期望能够达到整体的最优解。
贪心算法通常用于一些问题中，即每一步的选择只依赖于当前状态，而不考虑将来可能出现的情况。
贪心算法的适用条件：1. 贪心选择性质：贪心算法每一步都选择一个当前的最优解，此处的“最优”指的是局部最优。
这种最优选择可以确保问题能够被拆解，并且进行下一步求解。
2. 最优子结构性质：当问题的整体最优解能够通过局部最优解得到时，可以采用贪心算法求解。
这种情况下，问题的最优解可以由子问题的最优解推导出来。
3. 无后效性：贪心算法选择某一步操作时，只考虑当前状态，不会改变以前的操作，并且不关心未来的操作。
这种无后效性使得贪心算法在实际应用中操作简单、效率高。
贪心算法的基本步骤：1. 确定问题的局部最优解：贪心算法的核心是每一步都选择在当前情况下的最优解。
因此，需要确定问题如何拆解以及如何进行局部最优选择。
2. 定义问题的子问题：根据问题的最优子结构性质，将问题拆解为较小规模的子问题。
子问题应该是原问题的一个更小、更简单的实例。
3. 定义贪心选择策略：根据问题的特性，确定当前步骤下的最优选择策略。
这个选择应该是局部最优的，可以在不考虑子问题和整体未来状态的情况下得出。
4. 重复执行步骤2和3，直至求解出全局最优解。
贪心算法的优缺点：贪心算法具有简单易懂、快速高效的特点，适用于许多实际问题。
它可以避免穷举所有可能性，节省了计算时间。
此外，贪心算法常常能够找到近似最优解，尽管不一定能够保证全局最优解。
在实际问题中，近似最优解也往往可以满足实际需求。
然而，贪心算法并非适用于所有问题。
由于贪心算法只考虑当前状态的最优选择，而不考虑未来的影响，因此可能会导致局部最优解与全局最优解不一致。
贪心算法及几个常用的例题贪心算法：一、基本概念：所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。
也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。
必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
二、贪心算法的基本思路：1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
三、贪心算法适用的问题贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
实际上，贪心算法适用的情况很少。
一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。
四、贪心算法的实现框架从问题的某一初始解出发；while （能朝给定总目标前进一步）利用可行的决策，求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；五、贪心策略的选择因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
几个经典的例子：一、定义什么是贪心算法呢？所谓贪心算法是指，在对问题求解时，总是做出在当前看来最好的选择。
也就是说，不从整体最优解出发来考虑，它所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题都能产生整体最优解或整体最优解的近似解。
贪心算法的基本思路如下：1. .建立数学模型来描述问题。
2. 把求解的问题分成若干个子问题。
3. 对每个子问题求解，得到每个子问题的局部最优解。
4. 把每个子问题的局部最优解合成为原来问题的一个解。
实验三贪心算法实验目的1. 掌握贪心法的基本思想方法；2. 了解适用于用贪心法求解的问题类型，并能设计相应贪心法算法；3. 掌握贪心算法复杂性分析方法分析问题复杂性。
预习与实验要求1. 预习实验指导书及教材的有关内容，掌握贪心法的基本思想；2. 严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3. 认真听讲，服从安排，独立思考并完成实验。
实验设备与器材硬件：PC机软件：C++或Java等编程环境实验原理有一类问题是要从所有的允许解中求出最优解，其策略之一是“贪心法”，即逐次实施“贪心选择”：在每个选择步骤上做出的选择都是当前状态下最优的。
贪心选择依赖于在此之前所做出的选择，但不依赖于后续步骤所需要的选择，即不依赖于后续待求解子问题。
显然，这种选择方法是局部最优的，但不是从问题求解的整体考虑进行选择，因此不能保证最后所得一定是最优解。
贪心法是求解问题的一种有效方法，所得到的结果如果不是最优的，通常也是近似最优的。
实验内容以下几个问题选做一项：1. 用贪心法实现带有期限作业排序的快速算法应用贪心设计策略来解决操作系统中单机、无资源约束且每个作业可在等量时间内完成的作业调度问题。
假定只能在一台机器上处理N个作业，每个作业均可在单位时间内完成；又假定每个作业i都有一个截止期限di>0（它是整数），当且仅当作业i在它的期限截止以前被完成时，则获得pi的效益。
这个问题的一个可行解是这N个作业的一个子集合J，J中的每个作业都能在各自的截止期限之前完成。
可行解的效益值是J中这些作业的效益之和，即Σp。
具有最大效益值的可行解就是最优解。
2. 实现K元归并树贪心算法两个分别包含n个和m个记录的已分类文件可以在O（n+m）时间内归并在一起而得到一个分类文件。
当要把两个以上的已分类文件归并在一起时，可以通过成对地重复归并已分类的文件来完成。
例如：假定X1,X2,X3,X4是要归并的文件，则可以首先把X1和X2归并成文件Y1，然后将Y1和X3归并成Y2，最后将Y2和X4归并，从而得到想要的分类文件；也可以先把X1和X2归并成Y1，然后将X3和X4归并成Y2，最后归并Y1和Y2而得到想要的分类文件。
贪心算法及其应用近年来，随着科技的发展和数据的爆炸式增长，优化问题成为了研究的热点。
在高效解决各种优化问题中，贪心算法发挥了重要作用。
本文将介绍贪心算法的定义、特点、优缺点及其常见应用。
一、什么是贪心算法贪心算法是一种常见的算法方法，通过贪心策略来求解问题的最优解。
其思想是在每一个阶段上，选择当前最优解的策略，最终得到的就是问题的最优解。
二、贪心算法的特点贪心算法具有以下特点：1、局部最优解一定是全局最优解的一个组成部分；2、求解过程中不需要回溯；3、贪心算法具有高效性，时间复杂度低。
三、贪心算法的优缺点1、优点贪心算法具有简单、高效等优点。
对于那些没有明确要求最优解的问题，贪心算法是一个不错的选择。
2、缺点贪心算法的局限性在于，有些问题不能用贪心策略求得最优解。
因为每一步选择的最优解并不一定能导致全局最优解。
此外，贪心算法需要注意到问题的结构性质，否则可能做出错误决策。
四、贪心算法的应用1、背包问题背包问题是一个最经典的贪心算法应用场景。
在这个问题中，我们需要将一组物品放到一个容器中。
每个物品有一个权值和一个体积。
容器有一个最大承载体积，求容器可以承载的最大权值。
使用贪心算法在背包问题中是具有局限性的。
但是，在有些情况下，贪心策略是可行的。
例如在只考虑单个维度时，贪心算法以效率极高的速度求得其最优解。
2、最小生成树最小生成树问题是一个常见的求解问题。
其问题的目标是在一张图中找到一棵生成树，该树的所有边权之和最小。
在这个问题中，我们采用贪心策略选择当前最优边并添加到生成树中，以此来求得最优解。
3、哈夫曼编码哈夫曼编码是一种广泛应用的数据压缩算法。
其通过根据字符出现频率选择具有最小权值的二叉树节点，最终构建出哈夫曼树，以此来表示字符的编码信息。
使用哈夫曼编码可以实现对数据的高效压缩和解压缩。
4、调度问题在调度问题中，我们需要找到一种方案，让若干任务在满足约束条件的前提下，以最短的时间完成。
例如，在机器调度问题中，我们需要为不同机器安排任务以最小化整体完成时间。
贪心法(Greedy Approach)基本思想算法设计设计要素与动态规划法的比较正确性证明得不到最优解的处理办法应用实例1基本思想实例：最小生成树的Kruskal算法,活动选择问题适用问题：组合优化问题，满足优化原则设计方法：多步判断，解为判断序列选择依据：是否满足约束条件局部优化测度使用贪心法要解决的问题:是否可以得到最优解?不能得到最优解,解与最优解的误差估计2例1 活动选择问题S={1, 2, …, n}为n项活动的集合s i, f i分别为活动i 的开始和结束时间≥f j或s j≥f i活动i 与j相容当且仅当si求最大的两两相容的活动集思路：按结束时间递增顺序将活动排列为1,2,…,n, ≤f2≤…≤f n使得f1按照标号从小到大选择3定理1 算法Select 执行到第k步, 选择k项活动i1= 1, i2, …, ik, 那么存在最优解A包含i 1=1,i2, …, ik正确性证明根据定理：算法至多到第n步得到最优解67•证明存在最优解包含活动1•假设按照算法前k 步选择都导致最优解，证明第k +1步选择也导致最优解1. 第k 步：选择活动i 1=1, i 2, …, i k2. 归纳假设：存在最优解A ={i 1=1, i 2, …, i k }∪BB 是剩下的待选活动集S ’的一个最优解3. 由归纳基础，存在S ’的最优解B’包含i k +14. 由|B’|=|B | 知A’={i 1=1, i 2, …, i k }∪B’最优5. A’={i 1=1, i 2, …, i k , i k +1}∪(B’-{i k +1})最优. 对步数进行归纳的证明思路8归纳基础设S ={1,2,…,n }是活动集，活动按截止时间递增顺序排序.k =1, 证明存在最优解包含活动1.任取最优解A , A 中的活动按照截止时间递增的顺序排列. 如果A 的第一个活动为j ，j ≠1, 令A ’= (A −{j })∪{1}, 由于f 1≤f j , A ’也是最优解，且含有1.9}){'(},,...,{'},...,,{112121++−∪=∪k k k k i B i i i i B i i i 也是原问题的最优解.归纳步骤假设命题对k 为真,证明对k +1也为真.算法执行到第k 步, 选择了活动i 1=1, i 2, …, i k , 根据归纳假设存在最优解A 包含i 1= 1, i 2, …, i k , A 中剩下的活动选自集合S ’={ i | i ∈S , s i ≥f k },且A = {i 1, i 2, …, i k }∪BB 是S ’的最优解. 若不然, S ’的最优解为B*, B*的活动比B 多，那么B*∪{1, i 2, …, i k }是S 的最优解，且比A 的活动多,与A 的最优性矛盾.根据归纳基础，存在S ’的最优解B’含有S ’中的第一个活动，设为i k +1, 且|B ’|=|B |, 于是贪心算法的设计适用：满足优化原则的组合优化问题问题求解表示成多步判断整个判断序列对应问题的最优解子序列对应子问题的最优解贪心选择：确定一个优化测度不考虑以前的选择，只与当前状态有关以优化测度的极大(或极小)作为依据10贪心算法的设计（续）确定是否满足贪心选择性质具有贪心选择性质得到最优解，否则为近似解正确性证明：归纳法：证明贪心法得到最优解对算法步数归纳、对问题规模归纳交换论证：在保证最优性不变的前提下，从一个最优解出发进行逐步替换，最终得到贪心法的解自顶向下计算通过贪心选择，将原问题规约为子问题线性表记录选择的结果1113数学归纳法叙述一个可以归纳证明的命题：•对步数k 归纳对于任意k ，k 步贪心选择得到i 1,i 2,…,i k , 那么存在最优解包含i 1,i 2,…,i k •规模k 归纳：对于任意k ,贪心法得到关于规模为k 的问题的最优解归纳基础：k =1, 命题为真归纳步骤：假设对<k 的正整数命题为真，证明对k 命题也为真贪心选择性质的证明14ni x c x w x i i ni i ni i ,...,2,11,0max 11==≤∑∑==贪心法：将集装箱按照从轻到重排序，轻者先装例2 最优装载Loadingn 个集装箱1,2,…,n 装上轮船，集装箱i 的重量w i , 轮船装载重量限制为c ，无体积限制. 问如何装使得上船的集装箱最多？不妨设w i ≤c .贪心选择性质证明对规模的归纳•设集装箱标号按照从轻到重记为1,2,…,n •n=1,贪心选择得到最优解（只有1个箱子）•假设对于规模为n-1的输入得到最优解，证明对规模为n的输入也得到最优解15归纳步骤假设对于n-1个集装箱的输入，贪心法都可以得到最优解，考虑n个集装箱的输入N={1,2,…,n}, 其中w1≤w2≤…≤w n.由归纳假设，对于N’={2,3,…,n}，c’=c-w1, 贪心法得到最优解I’. 令I={1}∪I’，则I是关于N的最优解.若不然，存在包含1的关于N的最优解I*（如果I*中没有1，用1替换I*中的第一个元素得到的解也是最优解），且|I*|>|I|；那么I*−{1}是N’的解且|I*−{1}|>|I−{1}|=|I’|与I’的最优性矛盾.16说明Loading算法复杂性T(n)=O(n log n)Loading问题是0-1背包问题的特例：即v=1, i=1,2,…,n.i该问题是O(n log n)时间可解的0-1背包问题是NP难的。
1718贪心选择性质的证明交换论证例3 最小延迟调度问题任务集合S ，∀i ∈S ，d i 为截止时间，t i 为加工时间，d i , t i 为正整数.一个调度f :S →N ，f (i )为任务i 的开始时间. 求最大延迟达到最小的调度，即求f 使得}})({max {min i i Si f d t i f −+∈)()(or )()(,,,i f t j f j f t i f j i S j i j i ≤+≤+≠∈∀贪心策略选择从小到大安排任务贪心策略1：按照ti贪心策略2：按照d−t i从小到大安排任务i从小到大安排任务贪心策略3：按照di策略1 对某些实例得不到最优解.=1, d1=100, t2=10, d2=10反例：t1策略2对某些实例得不到最优解.反例：t=1, d1=2, t2=10, d2=10119算法设计1.Sort(S)使得d1≤d2 ≤…≤d n2. f(1)←0，i←23.while i≤n do4.f(i)←f(i−1)+t i-15.i←i+1从小到大选择按照截止时间di20交换论证——正确性证明算法的解的性质： 没有空闲时间, 没有逆序. 逆序(i,j): f(i)<f(j) and di>dj命题1 所有没有逆序、没有空闲时间的调度具有相同的最大延迟. 因为f1与f2都没有逆序，具有相同截止时间的任务必 须被连续安排. 在这些任务中最大延迟是最后一个任 务，被延迟的时间只与已安排任务加工时间之和 有关，与任务标号无关.21交换论证：从一个没有空闲时间的最优解出发，在不改变最优性的条件下，转变成没有逆序的解. (1) 如果一个最优调度存在逆序，那么存在i<n使得 (i,i+1)构成一个逆序. (2) 存在逆序(i,j)，j=i+1，那么交换i和j 得到的解的 逆序数减1，后面证明这个新的调度仍旧最优. (3) 至多经过n(n-1)/2次交换得到一个没有逆序的最 优调度.22证明：调度 f1, (i,j) 构成逆序, j=i+1, di>dj 交换 i与 j 得到 f2, f2比 f1不增加最大延迟时间(1) 交换 i, j 对其他任务的延迟时间没影响 (2) 交换后不增加 j 的延迟 (3) 任务i 在 f2 的延迟 L2i 小于任务 j 在 f1的延迟 L1j , 因 此小于f1的最大延迟 f1(i)=s f1(j)=s+ti f1(j)+tj =s+ti+tj i j f2(j)=s f2(i)=s+tj j i f2(i)=s+tj+tii 在 f2 结束时间 = j 在 f1 的结束时间 = s+ti+tj j 在 f1 的延迟: L1j = (s+ti+tj)−dj dj < di ⇒ L2i <L1j i 在 f2 的延迟: L2i = (s+ti+tj)−di23贪心法得不到最优解 的处理办法讨论对于哪些输入贪心选择能够得到最优解 输入应该满足的条件 讨论贪心法的解最坏情况下与最优解的误差 绝对误差与相对误差估计24确定得到最优解的输入 所满足的条件例4 找零钱问题 设有n种零钱, 重量分别为 w1, w2, ... , wn, 价值分别为 v1=1, v2, ... , vn. 付的总钱数是 y 如何付钱使得所付钱的总重最轻?25动态规划算法属于整数规划问题 动态规划算法可以得到最优解 设Fk(y)表示用前k种零钱，总钱数为y的最小重量 递推方程Fk +1 ( y ) =⎢ y ⎥ 0 ≤ x k +1 ≤ ⎢ ⎥ v ⎣ k +1 ⎦min{ Fk ( y − vk + 1 xk + 1 ) + wk + 1 xk +1 }⎢ y⎥ F1 ( y ) = w1 ⎢ ⎥ = w1 y ⎣ v1 ⎦26Greedy算法假设w1 w2 wn ≥ ≥ ... ≥ v1 v2 vn使用前k种零钱，总钱数为y 贪心法的总重为Gk(y)，则有如下递推方程⎢ y ⎥ Gk + 1 ( y ) = w k + 1 ⎢ ⎥ + Gk ( y mod vk +1 ) ⎣ vk +1 ⎦ ⎢ y⎥ G1 ( y ) = w1 ⎢ ⎥ = w1 y ⎣ v1 ⎦27n=2时得到最优解F1(y) = G1(y) ， F2(y) = G2(y)[ F1 ( y − v 2 ( x 2 + δ )) + w 2 ( x 2 + δ )] − [ F1 ( y − v 2 x 2 ) + w 2 x 2 ] = [ w1 ( y − v 2 x 2 − v 2δ ) + w 2 x 2 + w 2δ ] − [ w1 ( y − v 2 x 2 ) + w 2 x 2 ] = − w1v 2δ + w 2δ = δ ( − w1v 2 + w 2 ) ≤ 028n>2时得到最优解的判定条件定理2 假定 Gk(y)=Fk(y), vk+1>vk 且 vk+1 = pvk－δ, 0≤δ<vk, p∈Z+, 则以下命题等价.(1) G k +1 ( y ) ≤ G k ( y ) ( 2) G k +1 ( y ) = Fk +1 ( y ) ( 3) G k +1 ( pv k ) = Fk +1 ( pv k ) (4) w k +1 + G k (δ ) ≤ pw k用条件(4)需O(k)时间验证Gk+1(y)=Fk+1(y)? 对n种零钱作出验证, 可在O(n2)时间内完成29实验证 G3(y) = F3(y)例例 v1=1, v2=5, v3=14, v4=18, wi=1, i=1, 2, 3, 4. 对一切 y 有G1(y)=F1(y), G2(y)=F2(y). vk+1 = pvk－δ, 0≤δ<vk, p∈Z+, v3=14=3 v2－1, 即 p=3, δ=1.w k +1 + G k (δ ) ≤ pw kw3+G2(δ)=1+ G2(1) =1+1 = 2 pw2=3×1=3 w3+G2(δ)≤ p w23032例5 装箱问题有n 个物体, 长度分别为a 1,a 2,...,a n , a i ≤1,i =1,2,…,n . 要把它们装入长为1的箱子(只考虑长度的限制)问至少需要多少只箱子?mj B C B C a mj n i m j j i ,...,2,1,1)()(min 11=≤=∑∑==，C (B j ) 称为箱子B j 的装入量1—C (B j ) 称为箱子B j 的空隙近似解的误差估计例6 最优二元前缀码问题前缀码：用0-1字符串作为代码表示字符，要求任何字符的代码都不能作为其它字符代码的前缀非前缀码a---001, b---00, c---010, d---010100001: 01, 00, 001 d, b, a010, 00, 01 c, b, d前缀码的存储采用二叉树的结构，每个字符作为树叶，每个前缀码看作根到树叶的路径, x2, …, x n，输入：n个字符x1), i=1, 2, …, n.每个字符传输概率f(xi求：前缀码，使得平均传输一个字符的位数达到最小算法：Huffman树得到最优解3941例如a :45, b :13; c :12; d :16; e :9; f :5, Huffman树为平均位数：4*5%+4*9%+3*16%+3*12%+3*13%+1*45% = 2.24编码：f --0000, e --0001, d --001, c --010, b —011, a --1正确性证明•证明存在一个对应于最优前缀码的二叉树，以最小的频率作为树叶，且这两片树叶是兄弟•证明x, y 是树叶兄弟，z 是x, y 的父亲，z 的频率f[z]=f[x]+f[y], 令T ’= T−{x,y},则T ’是对应于最优前缀码C’= (C−{x,y})∪{z}的树4243则T 与T’的权之差为其中d T (i )为i 在T 中的层数（i 到根的距离）∑∑≥−=−∈∈Ci Ci T T i d i f i d i f T B T B 0)(][)(][)'()('引理1设C 是字符集，∀c ∈C , f [c ]为频率，x ,y ∈C , f [x ],f [y ]频率最小，那么存在最优二元前缀码使得x , y 的码字等长，且仅在最后一位不同.T →T’f [y ] ≤f [c ]f [x ] ≤f [b ]b 与x 交换c 与y 交换交换论证44引理2 设T 是最优解对应的树，∀x ,y ∈T , x ,y 是树叶兄弟，z 是x ,y 的父亲，z 的频率f [z ]=f [x ]+f [y ], 令T ’= T −{x ,y }, 则T ’是对应于最优前缀码C ’=(C −{x ,y })∪{z }的树证明：∀c ∈C −{x ,y },有d T (c )=d T ’(c ) ⇒f [c ]d T (c )=f [c ]d T ’(c ) 由d T (x ) =d T (y ) = d T ’(z ) +1得f [x ] d T (x ) + f [y ] d T (y ) = (f [x ] + f [y ]) (d T ’(z ) + 1)= f [z ]d T ’(z ) + (f [x ] + f [y ])从而B (T ) = B (T ’) + f [x ] + f [y ]若T ’不是关于C ’的最优树，那么存在T*使得B (T*)<B (T ’), z 是T*中的树叶，将x,y 加到z 上作为儿子，那么得到B (T*) + f [x ] + f [y ] < B (T )与T 的最优性矛盾.定理3 Haffman 算法得到最优前缀码算法•Huffman树的算法•时间O(n log n)49。
