贪心算法的实际应用
姓名：
班级：
学号：
指导老师：
定义：
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。
贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。
对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。
一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪心选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。
贪心算法可解决的问题通常大部分都有如下的特性：
⑴有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币。
⑵随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。
⑶有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
⑷还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。
⑸选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
⑹最后，目标函数给出解的值。
为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。
实例：
［最大整数］设有n个正整数，将它们连接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343，连成的最大整数为34331213。
又如：n=4时，4个整数7，13，4，246，连成的最大整数为7424613。
输入：n
N个数
输出：连成的多位数
算法分析：此题很容易想到使用贪心法，按这种标准，很容易找到反例：12，
121应该组成12121而非12112，那么是不是相互包含的时候就从小到大呢？也不一定，如12，123就是12312而非12123，这种情况就有很多种了。
解决方法：其实此题可以用贪心法来求解，只是刚才的标准不对，正确的标准是：先把整数转换成字符串，然后在比较a+b和b+a，如果a+b>=b+a，就把a 排在b的前面，反之则把a排在b的后面。
代码：
String str = "";
ArrayList
Scanner in = new Scanner(System.in);
System.out("Please input the number of data:");
int n = in.nextInt();
System.out("Please input the data:");
while (n-- > 0) {
array.add(in.next());
}
for(int i = 0; i < array.size(); i ++)
for(int j = i + 1; j < array.size(); j ++){
if((array.get(i) + array.get(j)).compareTo(array.get(j) + array.get(i)) < 0){
String temp = array.get(i);
array.set(i, array.get(j));
array.set(j, temp);
}
}
for(int i = 0; i < array.size(); i ++){
str += array.get(i);
}
System.out.println("str=:"+str);
}
小结：
贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。
个人觉得：贪心算法要比动态规划更难，因为动态规划一般是建立在一些递归之类的算法之上，加上记忆就可以达到效果。而贪心算法要考虑的东西却更多，特别是怎么证明局部最优就是全局最优。而一旦证明出来，贪心的代码则比较简单。
参考文献：
《The Art of Computer Programming》Donald E.Knuth著
《Introduction to Algorithms》Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein著
《算法与数据结构》傅清祥王晓东著
贪心算法经典例题 发布日期：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 贪心算法的应用 课程名称：算法设计与分析 院系：计算机科学与信息工程学院 学生姓名：**** 学号：********** 专业班级：********************************** 指导教师：****** 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) 《算法分析与设计》 课程实验 专业年级：信息与计算科学 学生学号： 学生姓名： 实验题目：用贪婪法求解背包问题 指导老师： 实验时间：20xx年xx月x日 一、实验内容 用贪婪法求解背包问题 要求：用非递归实现 二、实验步骤 2.1、理解算法思想和问题要求； 2.2、写出每个操作的算法 非递归算法： greedbag() { int N; int c; int[] w; int[] v; Scanner scan=new Scanner(System.in); System.out.print("输入背包的容量:"); c=scan.nextInt(); System.out.print("输入物品的数量:"); N=scan.nextInt(); System.out.print("分别输入物品的价值:"); v=new int[N]; for(int i=0;i 实验二贪心算法的应用 一、实验目的 1．掌握贪心算法的基本概念和两个基本要素 2．熟练掌握贪心算法解决问题的基本步骤。 3．学会利用贪心算法解决实际问题。 二、实验内容 1.问题描述： 题目二：会场安排问题 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法来进行安排。试编程实现对于给定的k个待安排活动，计算使用的最少会场。输入数据中，第一行是k的值，接下来的k行中，每行有2个正整数，分别表示k个待安排活动的开始时间和结束时间，时间以0点开始的分钟计。输出为最少的会场数。 输入数据示例 5 1 23 12 28 25 35 27 80 36 50 输出数据 3 三、算法分析 Stept1：输入各个活动的开始时间（s）和结束时间（e），初始化各活动的会场号。Step2：按活动的开始时间和活动时间排序，s最早（第一优先级）和持续时间最短（第二优先级）的活动排在最前。 Step3：执行贪婪算法，即s最早和持续时间最短的优先安排会场，并记录会场号，其余活动的s大于或等于已安排活动的e的安排在同一会场，若某活动的s 小于安排活动的e，则安排在另一会场，记录会场号，依次循环，直到所有活动均被安排。 Step4：统计会场号数，输出。 时间复杂度：O(n) 算法时间：O（nlogn） 核心算法: void swap(Active &a,Active&b) { Active t; t=a; a=b; b=t; } //活动时间排序 for(i=1;i<=k;i++) { for(j=i;j<=k;j++) { if(a[i].s>a[j].s) swap(a[i],a[j]); if(a[i].s==a[j].s) { if(a[i].e>a[j].e) swap(a[i],a[j]); } } } 四、程序调试及运行结果分析 五、源代码 贪心算法详解 贪心算法思想： 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本要素： 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 用背包问题来介绍贪心算法： 背包问题：有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要 求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 #include<> #define N 100 typedef struct bao{ int num; float w; float v; }; typedef struct avg{ int num; ( float val; float w; float v; }; struct bao b[N]; struct avg d[N]; int n; float c; ^ void Sort() { int i,j,k; struct avg temp[N]; for(i=0;i float x[N],sum = 0; for(i=0;i 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例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 算法分析与设计实验报告 第 4 次实验 } 附录：完整代码 #include 武汉理工大学 算法设计与分析论文题目：贪心算法应用研究 姓名：吴兵 学院：信息工程 专业班级：电子133 学号： 1409721303131 任课教师：张小梅 目录 摘要 (1) 1.绪论 (2) 2贪心算法的基本知识概述 (3) 2.1 贪心算法定义 (3) 2.2 贪心算法的基本思路及实现过程 (3) 2.3贪心算法的核心 (3) 2.4贪心算法的基本要素 (4) 2.5 贪心算法的理论基础 (6) 2.6 贪心算法存在的问题 (7) 3贪心算法经典应用举例 (8) 3.1删数问题 (8) 3.2 汽车加油问题 (10) 3.3会场安排问题 (12) 4.总结 (16) 5.参考文献 (17) 摘要 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的特点举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过贪心算法的特点来解决。 关键词：贪心算法最小生成树多处最优服务次序问题删数问题 贪婪算法在排课问题中分析与应用 摘要：排课问题是教学管理中重要的问题，对教学质量起到十分重要的影响。随着计算机和信息技术的快速发展，通过合理的算法编制排课系统是十分合适的。本文通过排课问题算法的分析，选择贪婪算法来解决排课问题。通过实验表明，目前的算法能够很好的解决排课问题，对问题的解决的复杂度大大降低，使得排课变得十分简单和高效。 关键字：排课，贪婪算法，优先级 1、绪论 在高校日常管理中，教学计划是重要的组成部分。而教学计划的重要体现方式之一就是排课表，其在教学管理中的地位和作用不可低估，课表的管理对教学管理是起到基础和重要的作用。因此排课问题是教学管理中重要的问题，对教学质量起到十分重要的影响。 由于上课约束条件多，课表的编制十分复杂，是一个耗时耗力的工作。目前随着高校人数的越来越多，其很难用手工去编制课表，其工作时间长，工作量大和繁琐的编制过程是一般人很难驾驭的。随着计算机和信息技术的快速发展，通过合理的算法编制排课系统是十分合适的。通过计算机算法的求解来对问题进行抽象和解决。 2、排课算法算法简介 目前对于排课问题的算法较多，主要有蚁群算法、模拟退火算法、遗传算法、整数规划法和贪婪算法等。 （1）蚁群算法 蚁群算法就是将模拟蚂蚁的活动，对参数设置较少。这种算法具备较强的全局搜索能力，但其效率较低，且容易出现停滞[1]。 （2）模拟退火算法 这个算法被较多的学者用来解决排课问题，它是模拟退火的现象，对自然事物进行抽象而来。其比较适合约束条件较少的问题。如果约束条件少，其很快就能获得最优解。但这种算法的参数选择较难，且资源开销大[2]。 （3）遗传算法 遗传算法是基于自然选择和生物遗传的全局优化策略。其优点在于在非线性问题上能够表现出全局最优，可以并行处理而且算法效率相对较高[3]。 但遗传算法本身较为复杂，由于排课问题的约束条件较多，其算法的效率较低，如果排课要求十分严格的话，很有可能造成找不到解。 （4）整数规划法 整数规划法来解决排课问题计算量很大，只适合规模较小排课问题，对于规模较大的，至今都很难找到一个可行算法。 （5）贪婪算法 贪婪算法是指在解决问题的时候，不会考虑整体最优，而是采取局部最优的思想进行最优思想[4]。也就是说，该算法将解决问题分解为每一个步骤，根据其难易程度进行解决，通过满足局部最优的方式来尽可能的获得最满意的解决。虽然在某些情况下，贪婪算法并不能得到最优解，但能得到相对满意的解。 3、排课问题综述 （1）排课原则 排课问题的本质是一个优化问题，是对教师、上课课程、上课时间和上课地点等因素的优化。其目的就是将全校所开设课程在有限的时间和地点下进行合理的安排，确保教学的顺利进行，以达到最优的效果。 为了能够产出一张满意合格的排课表，在排课中要满足一些约束条件。我们将一些约束 算法设计与分析实验报告 题目：贪心算法背包问题 专业：JA V A技术xx——xxx班 学号： 姓名： 指导老师： 实验三：贪心算法背包问题 一、实验目的与要求 1、掌握背包问题的算法 2、初步掌握贪心算法 二、实验题： 问题描述：与0-1背包问题相似，给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c。与0-1背包问题不同的是，在选择物品i装入背包时，背包问题的解决可以选择物品i的一部分，而不一定要全部装入背包，1< i < n。 三、实验代码 import java.awt.*; import java.awt.event.*; import javax.swing.*; public class er extends JFrame { private static final long serialVersionUID = -1508220487443708466L; private static final int width = 360;// 面板的宽度 private static final int height = 300;// 面板的高度 public int M; public int[] w; public int[] p; public int length; er() { // 初始Frame参数设置 this.setTitle("贪心算法"); setDefaultCloseOperation(EXIT_ON_CLOSE); setSize(width, height); Container c = getContentPane(); c.setLayout(new BoxLayout(c, BoxLayout.Y_AXIS)); setLocation(350, 150); // 声明一些字体样式 Font topF1 = new Font("宋体", Font.BOLD, 28); Font black15 = new Font("宋体", Font.PLAIN, 20); Font bold10 = new Font("宋体", Font.BOLD, 15); // 声明工具栏及属性设置 JPanel barPanel = new JPanel(); JMenuBar topBar = new JMenuBar(); topBar.setLocation(1, 1); barPanel.add(topBar); // 面板1和顶部标签属性设置 JPanel p1 = new JPanel(); JLabel topLabel = new JLabel("背包问题"); 贪心算法的应用实例 例2．排队问题 【题目描述】 在一个医院B 超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（0 答：贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。其有以下特性： ⑴ 有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币。 ⑵ 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。 ⑶ 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。 ⑷ 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。 ⑸ 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。 ⑹ 最后，目标函数给出解的值。 实验五应用贪心算法求解背包问题 学院：计算机科学与技术专业：计算机科学与技术 学号：班级：姓名： 、 实验内容： 背包问题指的是：有一个承重为W的背包和n个物品，它们各自的重量和价值分别是n ，假设W w i和v i（1 i n）w i 1i，求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。 二、算法思想： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 三、实验过程： #in elude { float p; // 物品效益 float w; // 物品重量 float X; // 物品该放的数量 int flag; // 物品编号 };// 物品信息结构体 void Insertionsort(goodinfo goods[],int n)// 插入排序，按pi/wi 价值收益进行排序，一般教材上按冒泡排序 { int j,i; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].p>goods[i].p) { } goods[i+1]=goods[0]; } }// 按物品效益，重量比值做升序排列goods[i+1]=goods[i]; i--; void bag(goodinfo goods[],float M,int n) { float cu; int i,j; 算法设计与分析实验报告 实验名称贪心算法实现背包问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1. 优化问题 有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解，称为最优解。 2.贪心法求优化问题 算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则（greedy criterion）。 3.一般方法 1）根据题意，选取一种量度标准。 2）按这种量度标准对这n个输入排序 3）依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。 procedure GREEDY(A，n) /*贪心法一般控制流程*/ //A(1：n)包含n个输入// solutions←φ //将解向量solution初始化为空／ for i←1 to n do x←SELECT(A) if FEASIBLE(solution，x) then solutions←UNION(solution，x) endif repeat return(solution) end GREEDY 4. 实现典型的贪心算法的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 1. 编程实现背包问题贪心算法。通过具体算法理解如何通过局部最优实现全局最优， 并验证算法的时间复杂性。 2.输入5个的图的邻接矩阵，程序加入统计prim算法访问图的节点数和边数的语句。 3.将统计数与复杂性函数所计算比较次数比较，用表格列出比较结果，给出文字分析。 三.程序算法 1.背包问题的贪心算法 procedure KNAPSACK(P，W，M，X，n) //P(1：n)和W(1；n)分别含有按 P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值 和重量。M是背包的容量大小，而x(1：n)是解向量 real P(1：n)，W(1：n)，X(1：n)，M，cu； integer i，n； X←0 //将解向量初始化为零 cu←M //cu是背包剩余容量 for i←1 to n do if W(i)>cu then exit endif X(i) ←1 cu←cu-W(i) repeat if i≤n then X(i) ←cu/ W(i) endif end GREEDY-KNAPSACK procedure prim(G,) status←“unseen” // T为空 status[1]←“tree node” // 将1放入T for each edge(1,w) do status[w]←“fringe” // 找到T的邻接点 dad[w] ←1; //w通过1与T建立联系 dist[w] ←weight(1,w) //w到T的距离 repeat while status[t]≠“tree node” do pick a fringe u with min dist[w] // 选取到T最近的节点 status[u]←“tree node” for each edge(u,w) do 修改w和T的关系 repeat repeat 2.Prim算法 实验报告 课程算法设计与分析实验实验名称贪心算法设计与应用第 1 页一、实验目的 理解贪心算法的基本原理，掌握贪心算法设计的基本方法及其应用； 二、实验内容 (一)Huffman编码和译码问题： 1．问题描述 给定n个字符在文件中的出现频率，利用Huffman树进行Huffman编码和译码。设计一个程序实现： 1.输入含n(n<=10)个字符的字符集S以及S中各个字符在文件中的出现频 率，建立相应的Huffman树，求出S中各个字符的Huffman编码。 2.输入一个由S中的字符组成的序列L，求L的Huffman 编码。 3. 输入一个二进制位串B，对B进行Huffman译码，输出对应的字符序列； 若不能译码，则输出无解信息。 提示：对应10 个字符的Huffman树的节点个数<211。 2．测试数据 Input n=5 字符集合S={a, b, c, d, e}, 对应的频率分别为 a: 20 b: 7 c: 10 d: 4 e: 18 字符序列L=ebcca 二进制位串B=01100111010010 Output S中各个字符的Huffman编码：（设Huffman树中左孩子的权<=右孩子的权）a: 11 b: 010 c: 00 d: 011 e: 10 L的Huffman 编码：10010000011 B对应的字符序列： dcaeeb 若输入的B=01111101001，则无解 (二) 加油问题（Problem Set 1702）： 1.问题描述 一个旅行家想驾驶汽车从城市A到城市B（设出发时油箱是空的）。给定两个 城市之间的距离dis、汽车油箱的容量c、每升汽油能行驶的距离d、沿途油站数n、油站i离出发点的距离d[i]以及该站每升汽油的价格p[i],i=1,2,…,n。设d[1]=0 贪心算法实现01背包问题 算法思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。 具体实现过程是：首先可以设置一个备份pvu类型的数组，在不破环原数据的情况下，对此备份数组按单位重量价值从大到小的排序。依次设立两个指针i，j(其中i表示当前应该参与最佳pv值的元素指针，j表示符合约束条件的指针（单位重量价值PV最大，重量最小，不超过最大承重量约束) 代码实现如下： #include 贪心算法的实际应用 姓名： 班级： 学号： 指导老师： 定义： 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪心选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。 贪心算法经典例题 在求解最优问题的过程中，依据某种贪心策略，从问题的初始状态出发，求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 【例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堆(0【精选】贪心算法的应用
算法设计实验_贪心算法背包问题
实验二 贪心算法的应用
贪心算法详解分析
C语言版贪心算法背包问题
贪心算法的应用
背包问题(贪心算法)
算法分析与设计选修课-贪心算法应用研究
贪婪算法在排课问题中分析与应用
贪心算法背包问题
贪心算法的应用实例
贪婪算法
c应用贪心算法求解背包问题
贪心算法实现背包问题算法设计与分析实验报告
贪心算法设计与应用
贪心算法实现01背包问题
贪心算法的实际应用
贪心算法经典例题
相关主题
文本预览