第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