贪心算法
贪心算法（Greedy Algorithm）
Lyon @ South China Algorithm University
2011 软件工程黎永盛
?Problem Description
?FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
?The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.
?Input
?The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers
M and N. Then N lines follow, each
contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.
?Output
?For each test case, print in a single line
a real number accurate up to 3 decimal
places, which is the maximum amount of JavaBeans that FatMouse can
obtain.Sample Input 5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1 Sample Output 13.333
31.500
What is GREEDY?
贪心法（Greedy algorithm），又称贪心算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。
在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。
Especially~
若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！
BEST 9506 吃水果
Description
Mr.chen买来了许许多多的水果来给那些acmers吃，但是由于最近大家都忙于比赛，所以呢只留下zyq在机房切题
但是lyd师兄十分喜欢吃水果，所以呢，就规定zyq一天只能吃一个。
每一个水果重量wi都不一定是一样的，而且都有一个食用期限ti。必须是在这个期限内把该水果给吃掉。
zyq就希望大家能写个程序帮他算出最多总共可以吃到多重的水果。
例如：
给出6个水果：
7 3
6 1
5 2
5 1
4 3
4 2
最多能够吃到：18=7+6+5
Solution
根据贪心的想法，因为要吃到总重量最大的水果，所以我们首先可以先按照重量大小进行排序（deadline先后是没有关系的），然后逐个水果填充到每天的安排中。
这么多天，填充到哪里？
假设我有两种水果(1, 1), (2, 2)，当我们填充重量是2的水果的时候，总不会把它放在第一天的时候吃吧？
于是可以想到，尽可能迟吃这个水果！这样是必定最优的~
Core Code Complexity : O(n^2)
* 代码中，first代表weight，second代表deadline。
因为这题的数据量比较小，所以我们可以这样直接找最靠后的一天。HDU -1789这题题意也是一样的，可是deadline的范围可以很大。还能不能用这种方法？
其实是可以的，只要加一个特判。想一想，如果deadline比物品数目多，说明什么？
Expansion
如果在上一题中，我批量进货水果，水果的数量多达10W个，甚至是100W个，O(n^2)算法显然不行。那么这题还能做吗？
怎么样可以使算法加速？
算法具体哪个操作是可以加速的？
枚举水果？这是肯定要的。
找水果放置的位置？好像能加速。
O(n)的找位置算法能用什么样的高效算法代替？
继续介绍后面的就离题了。。_(:з」∠)_
提示一下，这里可以用数据结构进行O(log n)的复杂度的维护，从而使整体的复杂度降到O(n log n)。
Simple Method for Greedy Problem 其实对于贪心的题，主要有两种做法：一种是yy出答案但不保证1y，另外一种是严谨的证明让bug无处可藏。
个人建议做题的时候要最好就是后面一种。当然，正式比赛的时候通常都是两者结合。面对稍微有点深度的贪心，先yy出基本做法，然后严谨的证明。
说到证明，看看下一题~
Crixalis's Equipment
?Problem Description
?Crixalis -Sand King used to be a giant scorpion(蝎子) in the deserts of Kalimdor. Though he's a guardian of Lich King now, he keeps the living
habit of a scorpion like living underground and digging holes.
?Someday Crixalis decides to move to another nice place and build a new house for himself (Actually it's just a new hole). As he collected a lot of equipment, he needs to dig a hole beside his new house to store them.
This hole has a volume of V units, and Crixalis has N equipment, each of them needs Ai units of space. When dragging his equipment into the hole, Crixalis finds that he needs more space to ensure everything is placed
well. Actually, the ith equipment needs Bi units of space during the
moving. More precisely Crixalis can not move equipment into the hole
unless there are Bi units of space left. After it moved in, the volume of the hole will decrease by Ai. Crixalis wonders if he can move all his equipment into the new hole and he turns to you for help.
Crixalis's Equipment
?题目大意：向一个容量为V的洞中搬物品每件物品有一个停放体积可一个移动体积问能否放下这些物品
?解题思路：对这些物品进行排序按照顺序依次进入洞中排序要尽可能使得所有的东西都能进入洞中（这是贪心常用的做法，对物品排序）
Input
The first line contains an integer T, indicating the number of test cases.
Then follows T cases, each one
contains N + 1 lines. The first line
contains 2 integers: V, volume of a
hole and N, number of equipment
respectively. The next N lines
contain N pairs of integers: Ai and Bi. 0 Output For each case output "Yes" if Crixalis can move all his equipment into the new hole or else output "No".Sample Input 2 20 3 10 20 3 10 1 7 10 2 1 10 2 11 Sample Output Yes No Solution 前面题透了一下，这题是对物品排序，然后扫一遍，判断是否能将所有的物品都放进洞穴里。 下面要说的就是如何排序？根据什么排序？ 假设有两种物品：(Ai, Bi)和(Aj, Bj) 如果要先放入物品i条件是什么？ 可以发现，如果要能先放入物品i，Ai+Bj要比Aj+Bi小。 这里Ai+Bj和Aj+Bi的意思就是如果物品i和j都能填充进去，放物品i 前至少需要剩余Ai+Bj的空间，放物品j前至少需要剩余Aj+Bi的空间。 这样一来，我们就可以知道，如果满足Ai+Bj 好了，两个物品的比较已经出来，对于这个贪心过程（也就是全局）是否也是这样呢？ 答案是肯定的，我们可以移项，变成Ai-Bi Core Code 思路清晰，代码还是很简练的。 Some Greedy Problems ?另外附上一些之前做过的贪心，之前做的这些比较多是结合数据结构的。 ?UVa Live Archive (google "Live Archive"即可找到入口) : 4636 4328 3507 4254?UVa : 10020 10012 ?HDU : 4415 3512 1677 Any questions? 谢谢观赏 WPS Office Make Presentation much more fun @WPS官方微博 @kingsoftwps 贪心算法经典例题 发布日期：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背包问题（贪心算法） 实验代码： #include 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.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 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) 贪心方法：总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。 应用：1：该问题可以通过“局部寻优”逐步过渡到“整体最优”。贪心选择性质与“动态规划”的主要差别。 2：最优子结构性质：某个问题的整体最优解包含了“子”问题的最优解。 代码如下： #include for(i=1;i<=n;i++) goods[i].X=0; cu=M; //背包剩余容量 for(i=1;i 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卷）2008学年第一学期考试科目：算法分析与设计 考试类型：（闭卷）考试时间：120 分钟 学号姓名年级专业 一、选择题（20分，每题2分） 1.下述表达不正确的是。 A．n2/2 + 2n的渐进表达式上界函数是O(2n) B．n2/2 + 2n的渐进表达式下界函数是Ω(2n) C．logn3的渐进表达式上界函数是O(logn) D．logn3的渐进表达式下界函数是Ω(n3) 2.当输入规模为n时，算法增长率最大的是。 A．5n B．20log 2n C．2n2 D．3nlog 3 n 3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是。A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog 2 n 4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨 牌的个数是。 A．（4k– 1）/3 B．2k /3 C．4k D．2k 5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算 法对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。 A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准 D．以上皆可行。但不同方法，算法复杂度上界可能不同 6.有9个村庄，其坐标位置如下表所示： 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在才能使到邮局到这9个村庄的总距离和最短。 A．（4.5，0）B．（4.5，4.5）C．（5，5）D．（5，0） 7.n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水， 水流恒定。如下说法不正确？ A．让水桶大的人先打水，可以使得每个人排队时间之和最小 B．让水桶小的人先打水，可以使得每个人排队时间之和最小 C．让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水D．若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样 8.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题， 分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。 【贪心算法】思想 & 基本要素 & 贪心算法与局部最优 & 贪心算法与动态规划的区别 & 运用贪心算法求解问题 首先我们先代入问题来认识一下贪心算法涉及的问题 找钱问题 给顾客找钱，希望找零的钞票尽可能少，零钱种类和数量限定 找钱问题满足最优子结构 最快找零（贪心）：为得到最小的找零次数，每次最大程度低减少零额活动安排问题 设个活动都需要使用某个教室，已知它们的起始时间和结束时间，求合理的安排使得举行的活动数量最多 贪心：使得每次安排后，教室的空闲时间最多 解决过程如下： 贪心算法求得的相容活动集是最大的 第一步：证明最优解中包含结束时间最早的活动 设相容集 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背包可以用动态规划？而不能用贪心算法 贪心易陷入局部最优 基于贪心算法与最小路径的基因组组装优化问题 摘要 随着人类基因组计划的实施和飞速发展，基因组测序拼接作为生物信息学的核有着极其重要的应用价值。新的测序技术大量涌现，产生的reads 长度更短，数量更多，覆盖率更大，能直接读取的碱基对序列长度远小于基因组长度。本文通过如何在保证组装序列的连续性、完整性和准确性的同时设计耗时短、内存小的组装算法，建立数学模型来解决基因组组装问题。 针对问题一，首先，利用相应的软件对原基因组G 进行切割，利用全基因鸟枪法测序对切割后的短基因进行测序，得到较小的基因组j i G ,通过对比多条任意切割后相似的基因组j i G 从而找出个别碱基对存在的识别错误。而对于基因组中存在的重复片段可以通过两个read 之间的DNA 片段的长度满足一定的分布规律即pared end read 来解决。 接下来对比任意两个11 1m n read 和3 2 2 m n read 是否相等，通过MATLAB 软件建立n m 阶的关联矩阵，最后利用图论中的最短路径方法使更多的基因组能拼接在一起，尽可能使拼接出来的基因组在原基因组的覆盖率达到最大。 针对问题二，先把附件给出的数据提取出来导入MATLAB 中，再结合问题一给出的模型对基因组进行重组，从而得到新的基因。 最后，基于对基因组组装的研究，为使重组基因能更接近原基因序列，对问题一提出模型进行合理性的评价。 关键词：基因组组装 全基因鸟枪法测序 贪心算法 最短路径 一、问题的重述 1.1问题背景 快速和准确地获取生物体的遗传信息对于生命科学研究具有重要的意义。对每个生物体来说，基因组包含了整个生物体的遗传信息，这些信息通常由组成基因组的DNA或RNA分子中碱基对的排列顺序所决定。获得目标生物基因组的序列信息，进而比较全面地揭示基因组的复杂性和多样性，成为生命科学领域的重要研究内容。 1.2问题提出 确定基因组碱基对序列的过程称为测序（sequencing）。测序技术始于20世纪70年代，伴随着人类基因组计划的实施而突飞猛进。从第一代到现在普遍应用的第二代，以及近年来正在兴起的第三代，测序技术正向着高通量、低成本的方向发展。尽管如此，目前能直接读取的碱基对序列长度远小于基因组序列长度，因此需要利用一定的方法将测序得到的短片段序列组装成更长的序列。通常的做法是，将基因组复制若干份，无规律地分断成短片段后进行测序，然后寻找测得的不同短片段序列之间的重合部分，并利用这些信息进行组装。例如，若有两个短片段序列分别为 ATACCTT GCTAGCGT GCTAGCGT AGGTCTGA 则有可能基因组序列中包含有ATACCTT GCTAGCGT AGGTCTGA这一段。当然，由于技术的限制和实际情况的复杂性，最终组装得到的序列与真实基因组序列之间仍可能存在差异，甚至只能得到若干条无法进一步连接起来的序列。对组装效果的评价主要依据组装序列的连续性、完整性和准确性。连续性要求组装得到的（多条）序列长度尽可能长；完整性要求组装序列的总长度占基因组序列长度的比例尽可能大；准确性要求组装序列与真实序列尽可能符合。 利用现有的测序技术，可按一定的测序策略获得长度约为50–100个碱基对的序列，称为读长（reads）。基因组复制份数约为50–100。基因组组装软件可根据得到的所有读长组装成基因组，这些软件的核心是某个组装算法。常用的组装算法主要基于OLC（Overlap/Layout/Consensus）方法、贪婪图方法、de Bruijn 图方法等。一个好的算法应具备组装效果好、时间短、内存小等特点。新一代测序技术在高通量、低成本的同时也带来了错误率略有增加、读长较短等缺点，现有算法的性能还有较大的改善空间。 具体解决问题如下： 问题一：试建立数学模型，设计算法并编制程序，将读长序列组装成基因组。你的算法和程序应能较好地解决测序中可能出现的个别碱基对识别错误、基因组中存在重复片段等复杂情况。 问题二：现有一个全长约为120,000个碱基对的细菌人工染色体（BAC），采用Hiseq2000测序仪进行测序，测序策略以及数据格式的简要说明见附录一和附录二，测得的读长数据见附录三，测序深度（sequencing depth）约为70×，即基因组每个位置平均被测到约70次。试利用你的算法和程序进行组装，并使之具有良好的组装效果。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例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堆(0 摘要：作业和测试的自动组卷是在线形成性考核系统的核心内容。本文在深入研究贪心算法的基础上，提出了基于贪心算法的自动组卷算法，分析了题库和作业库的约束条件，实现了快速高效的组卷过程。最后给出具体实例加以论证。该算法已经成功应用于实际的在线形成性考核系统中。 关键词：贪心算法；在线形成性考核；约束条件；组卷 一、引言目前，常用的自动组卷算法有随机选取算法、回溯试探算法、蛮力法和遗传算法等，这些算法对在线考试系统确实具有一定的应用价值，但这些方法生成的作业卷和测试卷在试卷的科学性和合理性上考虑较少。在综合研究以上各种算法的优缺点后，保证达到较好时间效率和空间效率的基础上，采用贪心算法为核心和随机选取算法为辅助的组卷算法，应用于在线形成性考核系统在线作业和在线测试中，能够达到较好的组卷效果，并且达到教学辅助效果。决定组卷效率和作业卷质量的主要因素有两个：一是题库和作业库的结构；二是组卷算法的设计。二、贪心算法简介贪心算法建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完整解为止。在每一步中，它要求“贪婪”地选择最佳操作，并希望通过一系列局部的最优选择，能够产生一个全局的最优解。贪心算法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法的基本要素。一是贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。二是最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。在题库组卷问题中，其最优子结构性质表现为：若a是对于e的题库组卷问题包含试题1的一个最优解，则相容作业卷集合a′= a-{1}是对于e′= {i∈e：si≥f1}的题库组卷问题的一个最优解。三、基于贪心算法的在线形成性考核系统组卷算法1、在线形成性考核系统结构在线形成性考核是指对学生学习过程的测评，是对学生课程学习的阶段性考核，是加强教学过程管理、检验学习效果的重要措施。在该系统中，管理员模块主要负责数据导入导出和系统维护，按照学生的课程注册信息绑定学生的班级、课程、辅导教师及恢复误删除成绩；教师模块完成课程形成性考核方案设计，作业题设计，查询考核内容，作业管理，作业批阅，查询批阅结果，删除已批阅但学生要求重做的作业成绩，学生信息管理，查询作业完成情况，到课率录入；学生模块主要功能是查看形考方案、主持教师、辅导教师、导学教师，在线作业，在线测试，作业成绩及反馈查询。在线形成性考核系统结构如图1所示。图1 在线形成性考核系统结构2、题库设计首先需要确定的是试题组织的方式。为了保证达标原则、全面性原则和主要性原则，最好将试题库与具体的知识内容进行关联，也即以课程知识点为核心组织试题库。然后就要考虑试题本身固有的特性参数，主要有题型、试题内容、答案、难度系数等。难度系数是试题难易程度的指标，也是试卷生成中的一个重要参数，它可以由教师录入试题时给定，并且在同一门课程中要坚持相同的标准，并且难度标准初始设定时要充分考虑到所要测试学生的程度范围。难度系数一般用等级来表示, 在五级难度系数中, 一级难度为最低, 五级难度为最高。题型分为客观题和主观题。客观题分单项选择题、多项选择选、判断题和填空题，主观题分计算题、简答题和论述题。3、作业库设计组卷方式可以按需求由主持老师进行客观题和主观题自由组卷。客观题在学生完成并提交成功后，系统自动阅卷并给出成绩。主观题在学生完成并提交后，由辅导老师阅 实验名称：贪心算法实例编程 求解最优服务次序问题 1、实验目的： 1)理解贪心算法的概念 2)掌握贪心算法的基本要素 3)掌握设计贪心算法的一般步骤 4)针对具体问题，能应用贪心算法设计有效算法 5)用C++实现算法，并且分析算法的效率 2、实验设备及材料： 硬件设备：PC机 机器配置：双核cpu频率2.2GHz,内存2G 操作系统：Windows 7 开发工具：VC++6.0 3、实验内容： ①问题描述 设有n个顾客同时等待一项服务。顾客i需要的服务时间为t i，1≤i≤n。 应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n恶搞顾客等待服务时间的总和除以n。 ②编程任务 对于给定的n个顾客需要的服务时间，计算最优服务次序。 ③样例 例如，现在有5个顾客，他们需要的服务时间分别为：56，12，5，99，33。 那么，按照所需服务时间从小到大排序为：5,12,33,56,99。排序后的顾客等待服务完成的时间为：5，17，50，106，205；和为：383；平均等待时间为：76.6。 4、实验方法步骤及注意事项： ①实验步骤 a、分析问题，确定最优的贪心选择； b、针对贪心选择过程进行算法设计； c、举例验证算法的正确性； d、上机调试算法。 ②解题思路 1)求解最优服务次序问题的贪心策略为：先为所需服务时间最短的顾客服务。 2)使用贪心算法求解最优服务次序问题的算法，用C++语言描述。 ①.最优值：(贪心算法) text(int n,int x[],int s[])//s[]为保存每个顾客等待时间的数组 { int i; int sum=0; for(i=0;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，（0 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 ：春阳哈夫曼编码 代码 #include 贪心算法 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）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪心选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。 Computer Knowledge and Technology 电脑知识与技术软件设计开发本栏目责任编辑：谢媛媛第6卷第35期(2010年12月)基于贪心算法的0-1背包问题 陈曦 （九江学院，江西九江332005） 摘要：贪心算法是解决问题的一种算法，因其解决问题时具有简单性、直观性和高效性而备受青睐。当待解决的问题具有最优子结构和贪心选择性质时，就可以考虑用贪心算法求解。0-1背包问题是计算机问题中一个普遍的问题，文章中详述了用贪心算法如何解决0-1背包问题。并得出用贪心算法求解此问题能得到最优解。 关键词：0-1背包；贪心算法；动态规划中图分类号：TP312文献标识码：A 文章编号：1009-3044(2010)35-10061-02 Based on the Greedy Algorithm of 0-1Knapsack Problems CHEN Xi (Jiujiang University,Jiujiang 332005,China) Abstract:The greedy algorithm is the solution to the problem of an algorithm,because of its solving problems with simplicity,intuitive and the efficiency is favour.When un-solved problems that have the most YouZi structure and moment-the greedy-choice properties,can con -sider to use greedy algorithm.0-1knapsack problems in computer problems is a common problem in the text,was described by the greedy algorithm to solve 0-1knapsack problems.And obtained by greedy algorithm for solving this problem can obtain optimal solutions.Key words:0-1knapsack;greedy algorithm;dynamic programming 1算法设计与分析是一门集应用性、创造性、实践性为一体的综合性极强的课程[1-2] 一个高效的程序不仅需要“编程技巧”，更需要合理的数据组织和清晰高效的算法。当一个问题具有最优子结构时，根据其具体情况可以用动态规划算法或者贪心算法来求解，但是问题同时具有贪心选择性质时，选择贪心算法更优，贪心算法通常会给出一个简单、直观和高效的解法[3]。 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法并不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。 作为一种算法设计技术，贪心法是一种简单的方法。与动态规划法一样，贪心法也经常用于解决最优化问题。不过与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。这种局部最优选择并不能保证总能获得全局最优解，但是通常能得到较好的近似最优解。例如，平时购物找钱时，为使找回的零钱的硬币数量最少，从最大面值的币种开始，按递减的顺考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小的面值的币种。这就是在采用贪心算法。这种方法在这里总是最优，因为银行对其发行的硬币种类和硬币面值的巧妙安排。如果只有面值分别为1,5,和11单位的硬币，而希望找回总额为15单位的硬币，按贪心算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币，但是最优的解答应是3个5单位面值的硬币。 1.1贪心算法解题思路 贪心算法[4]是经常用到的一种解题方法，往往在解决最优问题时都可以用贪心算法求解。其解题思路为： 1）建立数学模型来描述问题。 2）把求解的问题分成若干子问题。 3）对每一对问题求解，得到子问题的局部最优解。 4）把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进do 求出可行解的一个元素； 由所有解元素组合成问题的一个可行解。 虽然贪心算法有时并不能得到最优解，但是经过证明贪心算法能提高问题的解决效率。 收稿日期：2010-10-15 作者简介：陈曦（1982-），女，江西九江人，讲师，硕士，主要研究方向为计算机应用。 E-mail:xsjl@https://www.wendangku.net/doc/d29918173.html, https://www.wendangku.net/doc/d29918173.html, Tel:+86-551-56909635690964ISSN 1009-3044Computer Knowledge and Technology 电脑知识 与技术Vol.6,No.35,December 2010,pp.10061-1006210061贪心算法经典例题
贪心算法0-1背包问题(算法实验代码)
贪心算法详解分析
【精选】贪心算法的应用
背包问题的贪心算法
常见的贪心算法问题
2009.1算法设计与分析课程期末试卷-A卷(自测 )
贪 心 算 法
基于贪心算法与最短路径的基因组组装最优拼接问题---1411
贪心算法的应用
基于贪心算法的在线形成性考核系统组卷研究
贪心算法求解最优服务次序问题
贪心算法
贪心算法的应用实例
算法设计与分析实验报告贪心算法
贪心算法练习题
贪心算法的实际应用
基于贪心算法的0_1背包问题