《c语言精彩算法》由会员分享，可在线阅读，更多相关《c语言精彩算法（11页珍藏版）》请在金锄头文库上搜索。
1、C C 语言精彩算法语言精彩算法http:/www.fusc-ba.org/aspmaths/index.asp常用算法第 1 章 贪婪算法虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。本章首先引入最优化的概念，然后介绍一种直观的问题求解方法：贪婪算法。最后，应用该算法给出货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题
2、、最短路径问题、最小代价生成树等问题的求解方案。1.1 最优化问题本章及后续章节中的许多例子都是最优化问题（ optimization problem） ，每个最优化问题都包含一组限制条件（ c o n s t r a i n t）和一个优化函数（ optimization function） ，符合限制条件的问题求解方案称为可行解（ feasible solution） ，使优化函数取得最佳值的可行解称为最优解（optimal solution） 。例 1-1 渴婴问题 有一个非常渴的、聪明的小婴儿，她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水
3、，即婴儿可得到 n 种不同的饮料。根据以前关于这 n 种饮料的不同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下方法为每一种饮料赋予一个满意度值：饮用 1 盎司第 i 种饮料，对它作出相对评价，将一个数值si 作为满意度赋予第 i 种饮料。通常，这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满足她解渴的需要，但是不幸的是：具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设 ai 是第 i 种饮料的总量（以盎司为单位） ，而此婴儿需要 t 盎司的饮料来解渴，那么，需要饮用 n 种不同的饮料各多少量才能满足婴儿解渴的需求呢？设各种饮料的满意度已知。令 xi
4、 为婴儿将要饮用的第 i 种饮料的量，则需要解决的问题是：找到一组实数 xi（1in） ，使 n ?i = 1si xi 最大，并满足：n ?i=1xi =t 及 0xiai 。需要指出的是：如果 n ?i = 1ai k。寻找 1 ,n范围内最小的整数 j，使得 xjyj 。若没有这样的 j 存在，则 n ?i= 1xi =n ?i = 1yi 。如果有这样的 j 存在，则 jk，否则 y 就不是一个可行解，因为xjyj ，xj = 1 且 yj = 0。令 yj = 1，若结果得到的 y 不是可行解，则在 j+ 1 ,n范围内必有一个 l 使得 yl = 1。令 yl = 0，由于 wjw
5、l ，则得到的 y 是可行的。而且，得到的新 y 至少与原来的 y 具有相同数目的 1。经过数次这种转化，可将 y 转化为 x。由于每次转化产生的新 y 至少与前一个 y 具有相同数目的 1，因此 x 至少与初始的 y 具有相同的数目 1。货箱装载算法的 C + +代码实现见程序 1 3 - 1。由于贪婪算法按货箱重量递增的顺序装载，程序 1 3 - 1 首先利用间接寻址排序函数 I n d i r e c t S o r t 对货箱重量进行排序（见 3 . 5 节间接寻址的定义） ，随后货箱便可按重量递增的顺序装载。由于间接寻址排序所需的时间为 O (nl o gn)（也可利用 9 . 5
6、. 1 节的堆排序及第 2 章的归并排序） ，算法其余部分所需时间为 O (n)，因此程序 1 3 - 1 的总的复杂性为 O (nl o gn)。程序 13-1 货箱装船templatevoid ContainerLoading(int x, T w, T c, int n)/ 货箱装船问题的贪婪算法/ xi = 1 当且仅当货箱 i 被装载， 1=i=n/ c 是船的容量, w 是货箱的重量/ 对重量按间接寻址方式排序/ t 是间接寻址表int *t = new int n+1;I n d i r e c t S o r t ( w, t, n);/ 此时, wti = wti+1, 1=in/ 初始化 xfor (int i = 1;
