贪心算法1

贪心算法

贪心算法是一种符合人们日常思维习惯的简单有效的程序设计算法。贪心算法可用于求解最优问题。在信息学竞赛中常有它的用武之地。略举几个近年来竞赛中的题目就能见到运用贪心算法的踪影：

2006冬令营《风之韵》

2007 noip《纪念品分发》

2007 ioi 中国队选拔赛《挂坠》

2008noip《排序椅》

2008ioi 《传送器》

什么是贪心算法？顾名思义，贪心算法总是作出在当前看来是最好的选择。虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题都能产生整体最优解或是问题的次优解。因此有很好研究它的必要。

我们先来看看贪心算法在数据结构中的应用。求最小生成树的prim算法中，挑选的顶点是候选边中权值最小的边的一个端点，而加边法的kruskal算法中，更是首先将边的权值从小到大进行排序依次选取。

再看看求单源最短路径的算法。其基本算法思想是：设置顶点集合s并不断作贪心选择，来扩充这个集合，以最终求得最短路径。还有哈夫曼编码也用到贪心算法。

贪心算法和分治法及动态规划三者都具有子结构，都是将原问

题归纳为更小规模的相似的子问题，并通过求解子问题，最后获得整体解，三者有何不同呢？只有搞清三者的区别，才能很好地运用它们来解决问题。

首先是它们的子问题（或称子结构）是不同的。分治法中各子结构是独立的，动态规划一般具有重叠最优子结构，除了必须满足具有最优子结构外，还要满足无后效性。贪心算法要求问题具有最优子结构。

其次，在算法实现上看，分治法一旦递归地求出各子结构的解后，便可自下而上地将这些子结构解合并成问题的解。动态规划是所有子问题只计算一次并记录下来，以备后面的子问题使用，用空间换取时间, 所以求当前的解要依赖前面子结构的解。一般采用自底向上的递推方式求解。贪心法则是从上而下，从问题的初始阶段开始每个阶段作一个贪心的选择，不断将问题转换为规模更小的子问题，并期望通过每一次的局部最优选择达到全局最优。

贪心算法具有两个重要性质：①最优子结构性质②贪心选择性质

用好贪心算法关健是对一个问题能否运用贪心算法的判断和贪心标准的设计。对于一个问题能否用贪心算法要给出严格的证明是件比较困难的事，借助一个称为“拟阵”的工具，可以建立一个关于贪心算法的较一般的理论。这个理论在确定何时使用贪心算法可以得到问题的整体最优解十分有用。但是比较深奥难以理解。我们主要还是根据贪心算法的两个性质，以及运用反证法来证明。更

重要的是要通过编程实践多摸素、总结，从而掌握贪心算法。

另外运用贪心算法的思想与其它算法相配合，如“枚举+贪心”，“启发+随机化”多次贪心以及用于分支定界上等都有很好的效果。

下面通过一些例题来看看如何运用贪心算法。

例1.背包问题

【题目描述】

这是一大家很熟悉的背包问题。给定n种货物和一个载重量为m的背包。已知第i种货物的重量为wi ,其总价值为pi，编程确定一个装货方案，使得装入背包中货物的总价值最大。输出此总价值和装货方案。

【算法分析】

0，1背包问题对每种物品只有两种选择：选和不选，可用动态规划解决。而背包问题，可以选择物品的一部分装载，这样就可以把背包装满，用贪心算法可求得最优解。采用贪心标准是：选择单位重量价值高的货物优先装入，这样才能保证背包中所装货物总价值最大。而0，1背包用贪心算法却不能得到整体最优，为什么呢？我们来看一个例子：

有一背包容量为50千克，有三种货物：

物品1重10千克；价值60元；

物品2重20千克，价值100元；

物品3重30千克；价值120元。

总价值：（用贪心算法）

80+100+60=240

对于0，1背包问题，贪心选择之所以不能得到最

优解是因为它无法保证最终将背包装满，部分背包的

闲置使单位重量背包空间的价值降低。

例2．排队问题

【题目描述】

在一个医院B 超室，有n 个人要做不同身体部位的B 超，已知每个人需要处理的时间为ti ，（0

输入数据：第1行一个正整数n （你<=10000》，第2行有n

个不超过 1000的正整数ti.

输出要求：n个人排队时间最小总和。

输入输出样例

输入：4

5 10 8 7

输出：

67

【算法分析】

本题贪心算法：n个人时间从小到大排序，就是这n个人最佳排队方案。求部分和的和即为所求。

反证法证明：假设有最优解序列：s1,s2…sn,如s1不是最小的Tmin，不妨设sk=Tmin,将s1与sk对调，显然，对sk之后的人无影响，对sk之前的人等待都减少了，(s1-sk)>0,从而新的序列比原最优序列好，这与假设矛盾，故s1为最小时间，同理可证s2…sn依次最小。

例3．:数列极差问题

【题目描述】

在黑板上写了N个正整数做成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到

的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。

编程任务：对于给定的数列，编程计算出极差M。

输入输出样例：

输入：

4

2 1 4 3

输出：

13

【算法分析】

当看到此题时，我们会发现求max与求min是两个相似的过程。若我们把求解max与min的过程分开，着重探讨求max的问题。

下面我们以求max为例来讨论此题用贪心策略求解的合理性。

讨论：假设经（Ｎ－3）次变换后得到３个数：a ,b , max＇（max＇≥ａ≥ｂ），其中max＇是（Ｎ－２）个数经（Ｎ－３）次ｆ变换后所得的最大值，此时有两种求值方式，设其所求值分别为z1，z2，则有：z1＝(ａ×ｂ＋１）×max＇＋１，z2＝(ａ×max＇＋１）×ｂ+１所以z1－z2＝max＇－ｂ≥０若经（Ｎ－２）次变换后所得的３个数为：ｍ，ａ，ｂ（ｍ≥ａ≥ｂ）且ｍ不为（Ｎ－２）次变换后的最大值，即ｍ＜max＇则此时所求得的最大值为：z3＝（ａ×ｂ+１）×ｍ+１此时z1－z3＝(１+ａｂ）（max＇

－ｍ）＞０所以此时不为最优解。

所以若使第ｋ（１≤ｋ≤Ｎ－１）次变换后所得值最大，必使（ｋ－１）次变换后所得值最大（符合贪心策略的特点2），在进行第ｋ次变换时，只需取在进行（ｋ－１）次变换后所得数列中的两最小数ｐ，ｑ施加ｆ操作：ｐ←ｐ×ｑ+1，ｑ←≦即可（符合贪心策略特点1），因此此题可用贪心策略求解。在求ｍin时，我们只需在每次变换的数列中找到两个最大数ｐ，ｑ施加作用ｆ：ｐ←ｐ×ｑ+１，ｑ←-≦即可．原理同上。

这是一道两次运用贪心策略解决的一道问题，它要求选手有较高的数学推理能力。

贪心算法经典例题

贪心算法经典例题 发布日期：2009-1-8 浏览次数：1180 本资料需要注册并登录后才能下载！ ·用户名密码验证码找回密码·您还未注册？请注册 您的账户余额为元，余额已不足，请充值。 您的账户余额为元。此购买将从您的账户中扣除费用0.0元。 内容介绍>> 贪心算法经典例题 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④ 6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0

贪心算法0-1背包问题(算法实验代码)

实验三、0-1背包问题（贪心算法） 实验代码： #include int max(int a,int b) { if(a>b) return a; else return b; } void Knapsack(int *v,int *w,int *x,int c,int n, int m[8][100]) { int i,j; for(j=0;j=1;i--) { for(j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } for(i=1;i

printf("物品总数为：7\n"); printf("物品重量和价值分别为：\n"); printf("\n重量价值\n"); for (i=1;i<=n;i++) printf("%d %d \n",w[i],v[i]); int m=15; int array[8][100]={0}; Knapsack(v,w,x,m,7,array); printf("背包能装的最大价值为: %d\n",array[1][m]); printf("贪心算法的解为: "); for(i=1;i<=n;i++) { if(i==1) printf("%d",x[i]); else printf(" %d",x[i]); } printf("\n"); return 0; } 测试截图为：

计算机算法设计与分析习题和答案解析

《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（ A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数 19. （ D ）是贪心算法与动态规划算法的共同点。

贪心算法详解分析

贪心算法详解 贪心算法思想： 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本要素： 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 用背包问题来介绍贪心算法： 背包问题：有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要 求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

【精选】贪心算法的应用

贪心算法的应用 课程名称：算法设计与分析 院系：计算机科学与信息工程学院 学生姓名：**** 学号：********** 专业班级：********************************** 指导教师：****** 201312-27

贪心算法的应用 摘要：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法求问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 背包问题是一个经典的问题，我们可以采用多种算法去求解0/1背包问题，比如动态规划法、分支限界法、贪心算法、回溯法。在这里我们采用贪心法解决这个问题。 关键词：贪心法背包问题最优化

目录 第1章绪论 (3) 1.1 贪心算法的背景知识 (3) 1.2 贪心算法的前景意义 (3) 第2章贪心算法的理论知识 (4) 2.1 问题的模式 (4) 2.2 贪心算法的一般性描述 (4) 第3章背包问题 (5) 3.1 问题描述 (5) 3.2 问题分析 (5) 3.3算法设计 (5) 3.4 测试结果与分析 (10) 第4章结论 (12) 参考文献 (13) 附件 (13)

常见的贪心算法问题

4.5 哈夫曼编码 哈夫曼编码是一种被广泛应用而且非常有效的数据压缩技术，哈夫曼根据字符在文件中出现的不同频率来建立一个用0，1串表示各字符的最优编码树（称为哈夫曼树），它的设计也是贪心选择的一个典型例子。 例假设有一个包含10000个只含a，b，c，d，e，f字符的数据文件，各字符在文件中出现的频率见下4.5.1表 表 4.5.1 若采用等长编码，则需3位二进制数位来表示6个字符，这种方法要用30000位来表示整个文件。若采用变长编码，则整个文件只需 (45×1+13×3+12×3+16×3+9×4+5×4) ×100=22400 位 也就是说压缩了 (30000-22400)÷30000×100%≥25% 。实际上，这就是这个文件的最优编码方案了 4.5.1 前缀码 我们对每一字符规定一个0，1串作为其代码，并要求任一字符代码都不是其他字符代码的前缀，这样的编码简称为前缀码。在4.5.1表中的两种编码都是前缀码。由于任一字符代码都不是其他字符代码的前缀，所以译码方法非常简单。为了在译码过程中方便地取出编码的前缀，我们可以用二叉树作为前缀码的数据结构。在表示前缀码的二叉树中，树叶代表给定的字符，并将每个字符的前缀码看作是从树根到代表该字符的树叶的一条道路。代码中每一位的0或1分别作为指示某结点到左儿子或右儿子的路标。如图4-1中的两棵二叉树是表4.5.1中两种编码方案所对应的数据结构。

图 4-1 前缀码的二叉树表示 容易看出，表示最优编码方案所对应的前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子。而定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若C是编码字符集，包含有n个字符，则表示其最优前缀码的二叉树中恰好有n个叶子。每个叶子对应于字符集中一个字符，且该二叉树恰好有n - 1个内部结点。 4.6 最小生成树 设G= （V ，E ）是一个无向连通图，即一个网络。给 E 的每一条边（v, w ）赋于一个权。如果G 的一个子图G ˊ是一棵包含G 的所有顶点的树，则称G ˊ为G 的生成树。生成树上各边权的总和称为该生成树的代价。在G 的所有生成树中，代价最小的生成树称为G 的最小生成树。 网络的最小生成树在实际中有着广泛的应用。在不同的背景下，边的权可以代表不同的含义，比如，两点间的距离，两点间的公路造价等等。例如，在设计通信网络时，用图的顶点表示城市，用边（v, w ）的权表示建立城市v 和城市w 的之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。 用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节中要介绍的构造最小生成树的Prim 算法和Kruskal 算法都可以看作是应用贪心算法设计策略的典型例子。 4.6.1 Prim 算法 设G= （V ，E ）是一个连通带权图，V={1 ，2 ，···，n} ，二维数组W 的元素W[i][j] 表示边（i ，j ）的权。构造G 的一棵最小生成树的Prim 算法的基本思想是：首先置S={1} ，

贪 心 算 法

【贪心算法】思想 & 基本要素 & 贪心算法与局部最优 & 贪心算法与动态规划的区别 & 运用贪心算法求解问题 首先我们先代入问题来认识一下贪心算法涉及的问题 找钱问题 给顾客找钱，希望找零的钞票尽可能少，零钱种类和数量限定 找钱问题满足最优子结构 最快找零（贪心）：为得到最小的找零次数，每次最大程度低减少零额活动安排问题 设个活动都需要使用某个教室，已知它们的起始时间和结束时间，求合理的安排使得举行的活动数量最多 贪心：使得每次安排后，教室的空闲时间最多 解决过程如下： 贪心算法求得的相容活动集是最大的 第一步：证明最优解中包含结束时间最早的活动 设相容集 A 是一个最优解，其结束最早的活动为 a，则 ( A - { a }) U { 1 } 也是一个最优解 第二步：证明去掉结束时间最早的活动后，得到的子问题仍是最优的：反证法 理解贪心算法 贪心算法总是做出当前最好的选择 贪心选择的依据是当前的状态，而不是问题的目标

贪心选择是不计后果的 贪心算法通常以自顶向下的方法简化子问题 贪心算法求解的问题具备以下性质 贪心选择性质：问题的最优解可以通过贪心选择实现 最优子结构性质：问题的最优解包含子问题的最优解 贪心选择性质的证明 证明问题的最优解可以由贪心选择开始 即第一步可贪心 证明贪心选择后得到的子问题满足最优子结构 即步步可贪心 背包问题 问题描述：给定 n 个物品和一个背包。物品 i 的重量为 Wi ，价值为 Vi ，背包的容量为 c ，问如何选择物品或物品的一部分，使得背包中物品的价值最大？ 当 n = 3 ，c = 50 0-1背包问题：装入物品2、3，最大价值220 背包问题：装入物品1、2和2-3的物品3，最大价值240（贪心算法）贪心算法无法求解0-1背包问题，按贪心算法，0-1背包问题将装入物品1和2 贪心与局部最优 思考：为什么0-1背包可以用动态规划？而不能用贪心算法 贪心易陷入局部最优

贪心算法的应用

从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] ： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0v，则将a[i]-v张纸牌从第I堆移动到第I+1堆； （2）若a[i]

贪心算法

贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质： 1.整体的最优解可以通过局部的最优解来求出； 2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。 在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。 特别注意：若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！！ 以经典的活动安排为例： 1、若A是E的最优解，那么E-A 也是问题的最优解，在余下的问题里，继续拿最早结束的； 2、拿可以开始的最早结束。(所以要按结束时间排序一次，然后把可以开始的选择上，然后继续向后推) 贪心子结构是独立的（往往用标志判断而已），不同于动态规划（后面每一边的计算要用到前一步的值，另外开辟空间来保存） 贪心算法的基本步骤： 1、从问题的某个初始解出发。 2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。 3、将所有部分解综合起来，得到问题的最终解。 如最经典的活动安排问题，按结束时间从小到大排序，这样找出第一个节目后，剩下的节目已经是最safe的子结构了，再从子结构中最最早结束但又不和上一次观看的节目有冲突的节目 void arrange(int s[],int f[],bool A[],int n) { A[0] = true; int lastSelected = 0; for (int i = 1;i

贪心算法的应用实例

贪心算法的应用实例 例2．排队问题 【题目描述】 在一个医院B 超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（00,从而新的序列比原最优序列好，这与假设矛盾，故s1为最小时间，同理可证s2…sn依次最小。 例3．:数列极差问题 【题目描述】 在黑板上写了N个正整数做成的一个数列，进行如下操作：每一次擦去其中的两个数a 和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。 编程任务：对于给定的数列，编程计算出极差M。 输入输出样例： 输入： 4 2 1 4 3 输出： 13 【算法分析】 当看到此题时，我们会发现求max与求min是两个相似的过程。若我们把求解max与min的过程分开，着重探讨求max的问题。 下面我们以求max为例来讨论此题用贪心策略求解的合理性。 讨论：假设经（Ｎ－3）次变换后得到３个数：a ,b , max＇（max＇≥ａ≥ｂ），其中max＇是（Ｎ－２）个数经（Ｎ－３）次ｆ变换后所得的最大值，此时有两种求值方式，设其所求值分别为 z1，z2，则有：z1＝(ａ×ｂ＋１）×max＇＋１，z2＝(ａ×max＇＋１）×ｂ+１所以z1－z2＝max＇－ｂ≥０若经（Ｎ－２）次变换后所得的３个数为：ｍ，ａ，

贪心算法练习题

贪心算法 1.喷水装置（一） 描述 现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0

对于每一组输入，输出最多能够安排的活动数量。 每组的输出占一行 样例输入 2 2 1 10 10 11 3 1 10 10 11 11 20 样例输出 1 2 提示注意：如果上一个活动在T时间结束，下一个活动最早应该在T+1时间开始。 解题思路：这是一个贪心法中选择不相交区间的问题。先对活动结束时间从小到大排序，排序的同时活动的起始时间也要跟着变化。而且，结束时间最小的活动一定会安排，不然这段时间就白白浪费了。后一个活动的起始时间如果比前一个活动的结束时间大，即两个活动没有相交时间，就把这个活动也安排上。就这样一直找到结束时间最大的，输出时间数目即可。排序时可用下面的方法，排序的同时起始时间也跟着变了。 如果输入 0 6 3 4 1 9 2 8 则排序后的结果就是 3 4 0 6 2 8 1 9 Sample Output 3 5

贪心算法的实际应用

贪心算法的实际应用 姓名： 班级： 学号： 指导老师：

定义： 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪心选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。

大学计算机基础mooc习题集整理(含答案解析)

大学计算机考试模拟题（理工类） 一、简答题（本题共6个小题，每小题5分，共30分） 1. 什么是信息社会？信息社会的主要特征是什么？P32 第4题参见P13 P14 2. 什么是CPU，简述CPU的基本组成和功能P108 第18.(1) 参见P77 3. 什么是操作系统？简述操作系统的主要功能。P109 第24题参见P89 4. 人类问题求解的一般思维过程是什么？简要说明参见P112图3-1 描述 5. 什么是枚举法？说明枚举法的优缺点。参见P113第6段, P132穷举法 6. 什么是浏览器/服务器（B/S）三层体系结构，画图并简要说明。P340第10题参见P316 P276 二、单项选择题（本题共20个小题，每小题1分，共20分） 1. 下列容不属于信息素养（Information Literacy）的是 A．信息意识B．信息知识 C．分析能力D．信息道德 2. 阿兰·麦席森·图灵（Alan Mathison Turing）对计算机科学的发展做出了巨大贡献，下列说法不正确的是 A．图灵是著名的数学家、逻辑学家、密码学家，被称为计算机科学之父。 B．图灵最早提出关于机器思维的问题，被称为人工智能之父。 C．图灵创立了二进制。 D．“图灵奖”是为奖励那些对计算机科学研究与推动计算机技术发展有卓越贡献的杰出科学家而设立的。 3. 最早的机械式计算机“加法器”的发明人是 A．帕斯卡B．巴贝奇 C．莱布尼茨D．布尔 4. 巴贝奇的“分析机”到他终生都没有制造出来，下列说确的是（）

A．设计原理有错误B．设计精度不够 C．设计图纸不够完善D．机械加工的工艺水平达不到它要求的精度 5. 以集成电路为基本元件的第三代计算机出现的时间为（）。A．1965—1969B．1964—1975 C．1960—1969D．1950—1970 6. 在计算机中，引入16进制，主要目的是（）。 A．计算机中的数据存储采用16进制 B．计算机中的数据运算采用16进制 C．缩短2进制字串的长度 D．计算机的存地址采用16进制编制 7. 设计算机字长为16位，采用补码表示，可表示的整数的取值围是（）。A．0～65535B．-32767～32767 C．-32768～32767D．-32767～32768 8. 下列叙述中，正确的是( )。 A．所有十进制小数都能准确地转换为有限位二进制小数 B．汉字的计算机码就是国标码 C．所有二进制小数都能准确地转换为十进制小数 D．存储器具有记忆能力，其中的信息任何时候都不会丢失 9. 关于微处理器，下列说法错误的是（） A、微处理器就是微机的CPU，由控制器运算器和存储器组成。 B、微处理器不包含存储器。 C、微处理器执行CPU控制部件和算术逻辑部件的功能。 D、微处理器与存储器和外围电路芯片组成微型计算机。 10. 关于操作系统，下列叙述中正确的是（）。

贪心算法结课论文

贪心算法求解汽车加油问题 1 引言 随着科学的发展，人们生活中面临的大数据量越来越多。生活的快节奏要求人们对这些庞大的数据进行简单快速的处理，在这种实际需求的背景下，计算机算法设计得到了飞速发展，线性规划、动态规划、贪心策略等一系列运筹学模型越来越多被应用到计算机算法学中。 当一个问题具有最优子结构性质和贪心选择性质时，可用动态规划法来解决。但是贪心算法通常会给出一个更简单、直观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解，而且所给出的算法一般比动态规划算法更加简单、直观和高效[1]。 2 贪心算法 2.1 贪心算法概述 贪心算法又称贪婪算法，是指在求解问题时，总是做出在当前看来是最好的选择，也就是说，贪心算法并不要求从整体上最优考虑，它所作的仅是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。贪心算法并不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。 贪心算法可以简单描述为：对一组数据进行排序，找出最小值，进行处理，再找出最小值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。 贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准

智能算法30个案例分析

智能算法30个案例分析 【篇一：智能算法30个案例分析】 智能算法是我们在学习中经常遇到的算法，主要包括遗传算法，免 疫算法，粒子群算法，神经网络等，智能算法对于很多人来说，既 爱又恨，爱是因为熟练的掌握几种智能算法，能够很方便的解决我 们的论坛问题，恨是因为智能算法感觉比较“玄乎”，很难理解，更 难用它来解决问题。 因此，我们组织了王辉，史峰，郁磊，胡斐四名高手共同写作 matlab 智能算法，该书包含了遗传算法，免疫算法，粒子群算法， 鱼群算法，多目标pareto 算法，模拟退火算法，蚁群算法，神经网络，svm 等，本书最大的特点在于以案例为导向，每个案例针对一 个实际问题，给出全部程序和求解思路，并配套相关讲解视频，使 读者在读过一个案例之后能够快速掌握这种方法，并且会套用案例 程序来编写自己的程序。本书作者在线，读者和会员可以向作者提问，作者做到有问必答。 本书和目录如下：基于遗传算法的tsp算法（王辉） tsp (旅行商问题—traveling salesman problem)，是典型的np 完全问题，即其 最坏情况下的时间复杂性随着问题规模的增大按指数方式增长，到 目前为止不能找到一个多项式时间的有效算法。遗传算法是一种进 化算法，其基本原理是仿效生物界中的“物竞天择、适者生存” 的演 化法则。遗传算法的做法是把问题参数编码为染色体，再利用迭代 的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体。实践证明，遗传算法对于解决 tsp 问题等组合优化问题具有较好的寻优性能。 基于遗传算法和非线性规划的函数寻优算法（史峰）遗传算法提供 了求解非线性规划的通用框架，它不依赖于问题的具体领域。遗传 算法的优点是将问题参数编码成染色体后进行优化，而不针对参数 本身，从而不受函数约束条件的限搜索过程从问题解的一个集合开始，而不是单个个体，具有隐含并行搜索特性，大大减少陷入局部 最小的可能性。而且优化计算时算法不依赖于梯度信息，且不要求 目标函数连续及可导，使其适于求解传统搜索方法难以解决的大规模、非线性组合优化问题。 用于模式分类、模式识别等方面．但 bp 算法收敛速度慢，且很容易 陷入局部极小点，而遗传算法具有并行搜索、效率高、不存在局部

模式识别习题集答案解析

1、PCA和LDA的区别？ PCA是一种无监督的映射方法，LDA是一种有监督的映射方法。PCA只是将整组数据映射到最方便表示这组数据的坐标轴上，映射时没有利用任何数据部的分类信息。因此，虽然做了PCA后，整组数据在表示上更加方便（降低了维数并将信息损失降到了最低），但在分类上也许会变得更加困难；LDA在增加了分类信息之后，将输入映射到了另外一个坐标轴上，有了这样一个映射，数据之间就变得更易区分了（在低纬上就可以区分，减少了很大的运算量），它的目标是使得类别的点距离越近越好，类别间的点越远越好。 2、最大似然估计和贝叶斯方法的区别？p(x|X)是概率密度函数，X是给定的训练样本的集合，在哪种情况下，贝叶斯估计接近最大似然估计？ 最大似然估计把待估的参数看做是确定性的量，只是其取值未知。利用已知的样本结果，反推最有可能（最大概率）导致这样结果的参数值(模型已知，参数未知）。贝叶斯估计则是把待估计的参数看成是符合某种先验概率分布的随机变量。对样本进行观测的过程，把先验概率密度转化为后验概率密度，利用样本的信息修正了对参数的初始估计值。 当训练样本数量趋于无穷的时候，贝叶斯方法将接近最大似然估计。如果有非常多的训练样本，使得p(x|X)形成一个非常显著的尖峰，而先验概率p(x)又是均匀分布，此时两者的本质是相同的。 3、为什么模拟退火能够逃脱局部极小值？ 在解空间随机搜索，遇到较优解就接受，遇到较差解就按一定的概率决定是否接受，这个概率随时间的变化而降低。实际上模拟退火算法也是贪心算法，只不过它在这个基础上增加了随机因素。这个随机因素就是：以一定的概率来接受一个比单前解要差的解。通过这个随机因素使得算法有可能跳出这个局部最优解。 4、最小错误率和最小贝叶斯风险之间的关系？ 基于最小风险的贝叶斯决策就是基于最小错误率的贝叶斯决策，换言之，可以把基于最小错误率决策看做是基于最小风险决策的一个特例，基于最小风险决策本质上就是对基于最小错误率公式的加权处理。 5、SOM的主要功能是什么？怎么实现的？是winner-all-take-all 策略吗？ SOM是一种可以用于聚类的神经网络模型。 自组织映射（SOM）或自组织特征映射（SOFM）是一种使用非监督式学习来产生训练样本的输入空间的一个低维（通常是二维）离散化的表示的人工神经网络（ANN）。自组织映射与其他人工神经网络的不同之处在于它使用一个邻近函数来保持输入控件的拓扑性质。SOM网络中, 某个输出结点能对某一类模式作出特别的反应以代表该模式类, 输出层上相邻的结点能对实际模式分布中相近的模式类作出特别的反映,当某类数据模式输入时, 对某一输出结点产生最大刺激( 获胜结点) , 同时对获胜结点周围的一些结点产生较大刺激。在训练的过程中, 不断对获胜结点的连接权值作调整, 同时对获胜结点的邻域结点的连接权值作调整; 随着训练的进行, 这个邻域围不断缩小, 直到最后, 只对获胜结点进行细微的连接权值调整。 不是winner-all-take-all 策略。获胜结点产生刺激，其周围的结点也会产生一定程度的兴奋。 6、期望算法需要哪两步？请列出可能的公式并做必要的解释。 E-Step和M-Step。E-Step叫做期望化步骤，M-Step为最大化步骤。 整体算法的步骤如下所示： 1、初始化分布参数。 2、(E-Step)计算期望E，利用对隐藏变量的现有估计值，计算其最大似然估计值，以此实现期望化的过程。 3、(M-Step)最大化在E-步骤上的最大似然估计值来计算参数的值

贪心算法经典例题

贪心算法经典例题 在求解最优问题的过程中，依据某种贪心策略，从问题的初始状态出发，求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 【例1】均分纸牌（全国信息学奥林匹克分区联赛（NOIP）2002提高组（TG））。[问题描述]：有N堆纸牌，编号分别为1，2，…, N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N 的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4堆纸牌数分别为： ①9②8 ③17 ④6 移动3次可达到目的： 从③取4张牌放到④（9，8，13，10）→从③取3张牌放到②（9，11，10，10）→从②取1张牌放到①（10，10，10，10）。 [输入]：键盘输入文件名。 N（纸牌堆数，1<=N<=100） A1 A2 … AN（每堆初始纸牌张数，l<=Ai<=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。[输入输出样例]： a.in 4

9 8 17 6 屏幕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 这里用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0v，则将a[i]-v张纸牌从第I堆移动到第I+1堆； ⑵若a[i]

0-1背包问题的算法设计策略对比与讲解

算法设计与分析大作业 班级：电子154 姓名：吴志勇 学号： 1049731503279 任课老师：李瑞芳 日期： 2015.12.25

算法设计与分析课程论文 0-1背包问题的算法设计策略对比与分析 0 引言 对于计算机科学来说，算法的概念是至关重要的。在一个大型软件系统的开发中，设计出有效的算法将起到决定性的作用。通俗的讲，算法是解决问题的一种方法。也因此，《算法分析与设计》成为计算科学的核心问题之一，也是计算机科学与技术专业本科及研究生的一门重要的专业基础课。算法分析与设计是计算机软件开发人员必修课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和计算机专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。通过老师的解析，培养我们怎样分析算法的“好”于“坏”，怎样设计算法，并以广泛用于计算机科学中的算法为例，对种类不同难度的算法设计进行系统的介绍与比较。本课程将培养学生严格的设计与分析算法的思维方式，改变随意拼凑算法的习惯。本课程要求具备离散数学、程序设计语言、数据结构等先行课课程的知识。 1 算法复杂性分析的方法介绍 算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需的资源越多，该算法的复杂性越高；反之，所需资源越少，该算法的复杂性越低。对计算机资源，最重要的是时间与空间（即存储器）资源。因此，算法的复杂性有时间复杂性T(n)与空间复杂性S(n)之分。 算法复杂性是算法运行所需要的计算机资源的量，这个量应集中反映算法的效率，并从运行该算法的实际计算机中抽象出来，换句话说，这个量应该只依赖要解决的问题规模‘算法的输入和算法本身的函数。用C表示复杂性，N,I和A表示问题的规模、算法的输入和算法本身规模，则有如下表达式： C=F(N,I,A) T=F(N，I,A) S=F(N，I,A) 其中F(N,I,A)是一个三元函数。通常A隐含在复杂性函数名当中，因此表达式中一般不写A。 即：C=F(N,I) T=F(N,I) S=F(N,I) 算法复杂性中时间与空间复杂性算法相似，所以以下算法复杂性主要以时间复杂性为例： 算法的时间复杂性一般分为三种情况：最坏情况、最好情况和平均情况。下面描述算法复杂性时都是用的简化的复杂性算法分析，引入了渐近意义的记号O,Ω，θ，和o。 O表示渐近上界Ω表示渐近下界： θ表示同阶即：f(n)= O(g(n))且 f(n)= Ω（g(n)） 2 常见的算法分析设计策略介绍 2.1 递归与分治策略 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 递归算法举例： 共11页第1页