第4章 贪心方法
第4章 贪心方法
设计一个好的算法就像一门艺术。但仍然存在 些行之有效的能够用于解决许多问题的算法设计 方法，可以使用这些方法来设计算法。在许多情 况下，为了获得较好的性能，必须对这些算法进 行细致的调整。但在某些情况下，算法经过调整 之后仍然无法达到要求，这时就必须寻求另外的 方法来求解该问题。 从本章开始介绍一些与数据结构中不同的算法设计 方法：贪心法，动态规划，分枝限界法。其它的方 法还有：线性规划，整数规划，遗传算法，模拟退 火算法等等
从本章开始介绍一些与数据结构中不同的算法设计 方法：贪心法，动态规划，分枝限界法。其它的方 法还有：线性规划，整数规划，遗传算法，模拟退 火算法等等。 设计一个好的算法就像一门艺术。但仍然存在一 些行之有效的能够用于解决许多问题的算法设计 方法，可以使用这些方法来设计算法。在许多情 况下，为了获得较好的性能，必须对这些算法进 行细致的调整。但在某些情况下，算法经过调整 之后仍然无法达到要求，这时就必须寻求另外的 方法来求解该问题
4.1最优化问题 1.问题的一般特征 问题有n个输入，问题的解是由这n个输入的某个子集组 成，这个子集必须满足某些事先给定的条件。 约束条件：子集必须满足的条件； ·可行解：满足约束条件的子集；可行解可能不唯一； ÷目标函数：用来衡量可行解优劣的标准，一般以函数的形式 给出； 最优解：能够使目标函数取极值（极大或极小）的可行解
4.1 最优化问题 1. 问题的一般特征 问题有n个输入，问题的解是由这n个输入的某个子集组 成，这个子集必须满足某些事先给定的条件。 ❖约束条件：子集必须满足的条件； ❖可行解：满足约束条件的子集；可行解可能不唯一； ❖目标函数：用来衡量可行解优劣的标准，一般以函数的形式 给出； ❖最优解：能够使目标函数取极值（极大或极小）的可行解
例1[渴婴问题]有一个非常渴的、聪明的小婴儿，她可 能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果 汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得 到n种不同的饮料。根据以前关于这n种饮料的不同体验， 此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿 采取如下方法为每一种饮料赋予一个满意度值：饮用1盎 司第种饮料，对它作出相对评价，将一个数值s作为满意 度赋予第种饮料。 通常，这个婴儿都会尽量饮用具有最大满意度值的饮 料来最大限度地满足她解渴地需要，但是不幸地是：具有 最大满意度值地饮料有时并没有足够地量来满足此婴儿解 渴地需要。设a是第种饮料地总量，而此婴儿需要t盎司的 饮料来解渴，那么，需要饮用种不同的饮料各多少量才 能满足婴儿解渴的需求呢？
例1 [渴婴问题] 有一个非常渴的、聪明的小婴儿，她可 能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果 汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得 到n种不同的饮料。根据以前关于这n种饮料的不同体验， 此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿 采取如下方法为每一种饮料赋予一个满意度值：饮用1盎 司第i种饮料，对它作出相对评价，将一个数值si作为满意 度赋予第i种饮料。 通常，这个婴儿都会尽量饮用具有最大满意度值的饮 料来最大限度地满足她解渴地需要，但是不幸地是：具有 最大满意度值地饮料有时并没有足够地量来满足此婴儿解 渴地需要。设ai是第i种饮料地总量，而此婴儿需要t盎司的 饮料来解渴，那么，需要饮用n种不同的饮料各多少量才 能满足婴儿解渴的需求呢？
上述问题可形式描述如下： 输入：n,t,s,a(其中1≤in,n为整数，t、s、a为正实数)。 输出： 实数x1≤is,使之，x,最大，眨x,=0≤x,≤a, i= i=l 如果 ∑a,<t，则输出适当的错误信息。 i1 限制条件为∑x,=t(0≤x,≤a,) 优化函数为 任何满足限制条件的一组实数x都是可行解，而使 s,x,最大的可行解是最优解。 i=1
上述问题可形式描述如下： 输入：n,t,si ,ai (其中1in,n为整数，t、si、ai为正实数)。 输出：实数xi (1in)，使 最大，且 。 如果 ，则输出适当的错误信息。 = n i i a t 1 (0 ) 1 i i n i xi = t x a = = n i i i s x 1 限制条件为 (0 ) 1 i i n i xi = t x a = 优化函数为 = n i si xi 1 任何满足限制条件的一组实数xi都是可行解，而使 最大的可行解是最优解。 = n i i xi s 1
例2装箱问题]有一艘大船准备用来装载货物。所有待装 载货物都装在货箱中，且所有货箱的大小都一样，但货箱的 重量都各不相同。设第种货箱的重量为w(1≤i≤)，而货船 的最大载重量为C,我们的目标是在货船上装入最多的货物。 这个问题可以作为最优化问题进行描述：设存在一组标量×， 其可能取值为0或1。如果x为0，则货箱i不被装上船；如x 为1，则货箱将被装上船。我们的目的是找到一组x,使它 满足限制条件： 2w,x≤c,x∈{0,1}，1≤i≤n i 相应的优化函数是： x 满足限制条件的每一组x都是可行解，能使 取得最大值的方案是最优解
例2 [装箱问题] 有一艘大船准备用来装载货物。所有待装 载货物都装在货箱中，且所有货箱的大小都一样，但货箱的 重量都各不相同。设第i种货箱的重量为wi (1in )，而货船 的最大载重量为c，我们的目标是在货船上装入最多的货物。 这个问题可以作为最优化问题进行描述：设存在一组标量xi , 其可能取值为0或1。如果xi 为0，则货箱i不被装上船；如xi 为1，则货箱i将被装上船。我们的目的是找到一组xi ，使它 满足限制条件： 相应的优化函数是： = n i xi 1 = n i wi xi c xi i n 1 , {0,1} ,1 满足限制条件的每一组xi 都是可行解，能使 = n i xi 1 取得最大值的方案是最优解
例3[找零钱问题]一个小孩买了价值少于1元的糖，并将 1元钱交给了售货员。售货员希望用数目最少的硬币找给小 孩。假设提供了数目不限的面值为50分、10分、5分、2分、 1分的硬币。 可以通过解不定方程来解决这一问题。也可以分步骤组 成要找的零钱数，每次加入一个硬币。选择硬币时采用如下 准则：每一次选择应使零钱数尽量增大。为保证解的可行性， 所选择的硬币不应使零钱总数超过最终所需的数目。 假设需要找给小孩88分，首先选1枚50分的硬币，然后 选3枚10分硬币，再选1枚5分硬币，1枚2分硬币，1枚1分的 硬币。 问题：这样得到的硬币数目达到最少吗？ 类似问题：工资发放
例3 [找零钱问题] 一个小孩买了价值少于1元的糖，并将 1元钱交给了售货员。售货员希望用数目最少的硬币找给小 孩。假设提供了数目不限的面值为50分、10分、5分、2分、 1分的硬币。 可以通过解不定方程来解决这一问题。也可以分步骤组 成要找的零钱数，每次加入一个硬币。选择硬币时采用如下 准则：每一次选择应使零钱数尽量增大。为保证解的可行性， 所选择的硬币不应使零钱总数超过最终所需的数目。 假设需要找给小孩88分，首先选1枚50分的硬币，然后 选3枚10分硬币，再选1枚5分硬币，1枚2分硬币，1枚1分的 硬币。 问题：这样得到的硬币数目达到最少吗？ 类似问题：工资发放
例4[最小代价通讯网络]城市之间所有可能的通信连接 可被视作一个无向图，图的每条边都被赋予一个权值，权值 表示建成由这条边所表示的通信连接所要付出的代价。包含 图中所有顶点（城市)的连通子图都是一个可行解。设所有 权值都为负，则所有可能的可行解都可表示成无向图的一组 生成树，而最优解就是其中具有最小代价的生成树。 在这个问题中，需要选择一个无向图中的边集合的子集， 这个子集必须满足如下限制条件：所有的边构成一个生成树。 而优化函数是子集中所有边的权值之和。 例5[最短路径问题]在有向图中求一个顶点到另一个顶 点的最短路径。（如路由问题）
例4 [最小代价通讯网络] 城市之间所有可能的通信连接 可被视作一个无向图，图的每条边都被赋予一个权值，权值 表示建成由这条边所表示的通信连接所要付出的代价。包含 图中所有顶点（城市）的连通子图都是一个可行解。设所有 权值都为负，则所有可能的可行解都可表示成无向图的一组 生成树，而最优解就是其中具有最小代价的生成树。 在这个问题中，需要选择一个无向图中的边集合的子集， 这个子集必须满足如下限制条件：所有的边构成一个生成树。 而优化函数是子集中所有边的权值之和。 例5 [最短路径问题] 在有向图中求一个顶点到另一个顶 点的最短路径。（如路由问题）
例6[机器调度]现有件任务和无限多台机器，任务可以 在机器上得到处理。每件任务的开始时间为$，完成时间 为f,S<f。[s,f]为处理任务的时间范围。两个任务1， 重叠是指两个任务的时间范围区间重叠，而并非是指，的起 点或终点重合。一个可行的任务分配是指在分配中没有两件 重叠的任务分配给同一台机器。因此，在可行的分配中，每 台机器在任何时刻最多只处理一个任务。最优分配是指使用 的机器最少的可行分配方案。 假设有n=7件任务，标号为a到g。它们的开始于完成时间如下： 任务 a b c d e f g 开始 0349 716 完成 277111058 若将任务a分给机器M1,任务b分给机器M2,.,任务g分给机器M7这种 分配是可行的分配，共使用了7合机器。但它不是最优分配。因为若将a、 b、d分配给同一台机器，则机器数目降为5台
例6 [机器调度] 现有n件任务和无限多台机器，任务可以 在机器上得到处理。每件任务的开始时间为si ，完成时间 为fi ， si <fi 。[si ,fi ]为处理任务i的时间范围。两个任务i,j 重叠是指两个任务的时间范围区间重叠，而并非是指i,j的起 点或终点重合。一个可行的任务分配是指在分配中没有两件 重叠的任务分配给同一台机器。因此，在可行的分配中，每 台机器在任何时刻最多只处理一个任务。最优分配是指使用 的机器最少的可行分配方案。 假设有n=7件任务，标号为a到g。它们的开始于完成时间如下： 任务 a b c d e f g 开始 0 3 4 9 7 1 6 完成 2 7 7 11 10 5 8 若将任务a分给机器M1,任务b分给机器M2,…,任务g分给机器M7这种 分配是可行的分配，共使用了7台机器。但它不是最优分配。因为若将a、 b、d分配给同一台机器，则机器数目降为5台
最优化问题求解分类：根据描述问题约束条 件和目标函数的数学模型的特性和问题的求解方 法的不同，可分为：线性规划、整数规划、非线 性规划、动态规划等。 贪心方法：一种改进的分级的处理方法，可对 满足上述特征的某些问题方便地求解
最优化问题求解分类：根据描述问题约束条 件和目标函数的数学模型的特性和问题的求解方 法的不同，可分为：线性规划、整数规划、非线 性规划、动态规划等。 贪心方法：一种改进的分级的处理方法，可对 满足上述特征的某些问题方便地求解