贪心算法求解汽车加油问题
1 引言
随着科学的发展，人们生活中面临的大数据量越来越多。生活的快节奏要求人们对这些庞大的数据进行简单快速的处理，在这种实际需求的背景下，计算机算法设计得到了飞速发展，线性规划、动态规划、贪心策略等一系列运筹学模型越来越多被应用到计算机算法学中。
当一个问题具有最优子结构性质和贪心选择性质时，可用动态规划法来解决。但是贪心算法通常会给出一个更简单、直观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解，而且所给出的算法一般比动态规划算法更加简单、直观和高效[1]。
2 贪心算法
2.1 贪心算法概述
贪心算法又称贪婪算法，是指在求解问题时，总是做出在当前看来是最好的选择，也就是说，贪心算法并不要求从整体上最优考虑，它所作的仅是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。贪心算法并不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。
贪心算法可以简单描述为：对一组数据进行排序，找出最小值，进行处理，再找出最小值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。
贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的。
贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。
对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准
是使用贪婪算法的核心。
一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。
2.2 贪心算法的基本要素
贪心算法通过一系列的选择得到问题的解，它所做的每一个选择都是当前状态下局部最好选择，即贪心选择。
但是对于一个问题，怎么知道是否可以用贪心算法解决此问题，以及能否得到问题的最优解呢？这个问题难以给予肯定的回答。但是，我们从许多可以用贪心算法求解的问题中看到这类问题一般具有两个重要的性质：贪心选择性和最优子结构性质。
贪心选择性是指所求问题的整体最优解可以通过一系列局部最优的选择得到。因此，对于一个具体问题，它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终可以得到整体最优的结果，即通过贪心选择后，原问题被简化为规模更小的类似子问题。
而最优子结构性质，主要是指原问题的最优解包含子问题的最优解。
2.3 贪心算法的特性
通过对比能够用贪心算法解决的诸多问题，我们不难总结出贪心算法能够解决的问题的一系列特性：
（1）存在一个最优的方法来解决的问题。为了构造问题的解决方案,有一个候选的对象是一个集合：比如不同面值的硬币。
（2）随着算法的进行，将产生两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但是被丢弃的候选对象。
（3）算法中将产生一个用来检查一个候选对象是否提供了问题的解答的函数。当然，该函数并不考虑此时的解决方法是否最优。
（4）算中法另一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。
（5）选择函数指出哪一个剩余的候选对象可能构成问题的解。
（6）最后返回解的值。
为了解决原问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数,使得贪婪算法一步一步的进行。起初,算法选出的候选对象的集合为空，接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象，然后加入到一个集合中，如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑。每一次都扩
充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。
2.4 贪心算法的基本思路
用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法思想的本质就是分治，或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。
利用贪心策略解题，需要解决两个问题：
（1）该题是否适合于用贪心策略求解；
（2）如何选择贪心标准，以得到问题的最优/较优解。
具体的实现过程如下：
（1）建立数学模型来描述问题。
（2）应用同一规则F，将原问题变为一个相似的、但规模更小的子问题。
（3）对每一子问题求解，得到子问题的局部最优解。
（4）把子问题的解局部最优解合成原来解问题的一个解。
实现的算法的过程如下：
从问题的某一初始解出发；
while（能朝给定总目标前进一步）
do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解。
3 经典例子分析
3.1 0-1背包问题
0-1背包问题：给定n种物品和一个背包。物品i的重量和价值分别是w i和v i，背包的容量为C。要求正确的选取装入背包的物品，使得装入背包的物品价值之和最大。例如：C=30物品：A B C
重量：28 12 12
价值：30 20 20
根据贪心选择策略，首先选择A，然后再比较B、C，无法再装入。可以看出，最终的结果是将A装入背包中。但是，如不按贪心算法求解，实际是装入B和C最好。
因此，对于0-1背包问题，贪心选择不能达到结果最优，这是因为在这种情况下，无法保证最终将背包装满，部分闲置的空间使得每公斤背包的价值下降了。因此，在考虑此类的背包问题时，应该比较选择该物品呵不选择该物品所导致的最终方案，然后再做出最好的选择，此时可用动态规划算法求解。
显然，对于以上例子，如果不要求选择物品的全部装入背包，允许我们只选择部分装入
背包，此问题及转化为普通背包问题。此时即可用贪心选择算法求解。一般步骤为：首先选择将每公斤价值最大的物品装入背包，如果背包未满，再选择每公斤价值次大的物品装入，以此类推。
3.2 加油站问题（习题4-16）
（一）问题描述
一辆汽车加满油后可行驶N公里。旅途中有若干个加油点。设计一个有效算法，指出应在哪些加油站加油，使得旅途中加油次数最少，并证明算法能产生一个最优解。
（二）问题分析
设汽车在起点已经为加满油的状态，记加油的次数为k，起点与终点距离为S，加油站的个数为n，加油站i与加油站i+1之间的距离存放在一个数组a[i]中（i=0、1、2、3…..n），其中a[0]表示汽车位于起始点,a[n+1]表示汽车到达终点。对于原问题，主要有以下几种情况：
A 当S B 当S>N时： （1）各加油站之间的距离相等且等于N，即a[i]=N，需要加油次数至少为k=n； （2）各加油站之间的距离相等且大于N，即a[i]>N，则不可能到达终点。 （3）各加油站之间的距离相等且小于N，即a[i] k=[n/N]+1(n%N！=0)； （4）各加油站之间的距离不相等，即a[i]!=a[j]，则加油次数k可以通过以下算法得到。 具体算法描述如下： int add(int b[ ],int m,int n) { //求一个从m到n的数列的和 int sb; for(int i=m;i return sb; } int Tanxin(int a[n], int N) //a[n]表示加油站的个数，N为加满油能行驶的最远距离 { int b[n]; //若在a[i]加油站加油，则b[i]为1，否则为0 int m=0; if(a[i]>N) return ERROR; //如果某相邻的两个加油站间的距离大于N，则不能到达终点 if(add(a[i], 0, n) { //如果这段距离小于N，则不需要加油 b[i]=0; return add(b[i],0,n); } if(a[i]==a[j]&&a[i]==N) { //如果每相邻的两个加油站间的距离都是N，则每个加油站都需要加油 b[i]=1; return add(b[i],0,n); } if(a[i]==a[j]&&a[i] { //如果每相邻的两个加油站间的距离相等且都小于N if( add(a[i],m,k) < N && add(a[i],m,k+1) > N ) { b[k]=1; m+=k; } return add(b[i],0,n); } if(a[i]!=a[j]) { //如果每相邻的两个加油站间的距离不相等且都小于N if( add(a[i],m,k) < N && add(a[i],m,k+1) > N ) { b[k]=1; m+=k; } return add(b[i],0,n); } viod main( ) { int a[ ]; scanf("%d",a); scanf("/n"); scanf("/d",&N); Tanxin(a[ ],0,n); } 由于贪心算法适用的问题必须满足连个属性：贪心性质和最优子结构，因此，对于该汽车加油的问题是否适合用贪心算法，要先判定其是否具有这两个性质。 ●贪心选择性质 对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的N千米这段路程上任取两个加油站Ａ、Ｂ，且Ａ距离始点比Ｂ距离始点近，则若在Ｂ加油不能到达终点那么在Ａ加油一定不能到达终点，因为m+N ●最优子结构 由于（b[1]，b[2]，……b[n]）是这段路程加油次数最少的一个满足贪心选择性质的最优解，则易知若在第一个加油站加油时，b[1]=1，则（b[2]，b[3]，……b[n]）是从a[2]到a[n]这段路程上加油次数最少且这段路程上的加油站个数为（a[2]，a[3]，……a[n]）的最优解，即每次汽车中剩下的油不能在行驶到下一个加油站时我们才在这个加油站加一次油，每个过程从加油开始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。 4总结与心得 贪心算法是常见的算法之一，是一种重要的算法涉及策略，有简单、直接、高效的特点。按照贪心算法设计出来的许多算法均能得到结果的最优，虽然它不能保证对每一个问题最后的解都是最优的。贪心算法所作出的选择依赖于以往所做过的选择，绝不依赖将来的选择，这使得算法在编码和执行过程中都有一定的速度优势。 对于一个问题的最优解只能用穷举法得到时，用贪心算法是寻找问题最优解的较好算法。对一个问题可以同时用几种方法解决，贪心算法并不是对所有的问题都能得到整体最优解或是最理想的近似解时，就需判断贪心性质的正确性了。总之，如果一个贪心解决方案存在，就可以使用它。 通过将贪心算法应用到实例——汽车加油问题上，更加深刻的理解了贪心算法的方便与简单之处。不难看出，贪心算法将会在各个领域，尤其是科学计算和工程中的应用越来越广泛。 参考文献： [1] 王晓东.计算机算法设计与分析 [M]．北京：电子工业出版社,2007． [2] 严蔚敏,吴伟民.数据结构(c语言版)[M].北京:清华大学出版社,1997． [3] 谭浩强.C++面向对象程序设计[M].北京:清华大学出版社,2006． 实验三、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; } 测试截图为： 贪心算法经典例题 发布日期：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 结构优化课程设计 学院土木学院 专业工程力学 班级1001 学号100120118 姓名崔亚超 总结结构优化设计的原理、方法及发展趋势 崔亚超 工程力学1001班学号100120118 摘要：阐述了工程结构优化设计理论从最初的截面优化发展到形状优化、拓扑优化的基本历程及其相关特点，对优化设计选用的各种算法进行归类，并简述结构优化设计的发展趋势。 关键词：尺寸优化；形状优化；拓扑优化；优化算法 Summary structural optimization design principles, methods and development trends Abstract:The structural optimization of engineering design theory from the initial cross-section to optimize the development of shape optimization, topology optimization of the basic course and its related characteristics, the optimum design on the range of algorithms are classified, and to outline the development trend of structural optimization design . Key words:size optimization; shape optimization; topology optimization; optimization algorithm 0 引言 结构优化设计的目的在于寻求既安全又经济的结构形式，而结构形式包括了关于尺寸、形状和拓扑等信息I对于试图产生超出设计者经验的有效的新型结构来说，优化是一种很有价值的工具，优化的目标通常是求解具有最小重量的结构B同时必须满足一定的约束条件，以获得最佳的静力或动力等性态特征。 集计算力学、数学规划、计算机科学以及其他工程学科于一体的结构优化设计是现代构设计领域的重要研究方向。它为人们长期所追求最优的工程结构设计尤其是新型结构设计提供了先进的工具，成为近代设计方法的重要内容之一。 结构优化设计也使得计算力学的任务由被动的分析校核上升为主动的设计与优化，由此结构优化也具有更大的难度和复杂性。它不仅要以有限元等数值方法作为分析手段，而且还要进一步计算结构力学性态的导数值。它要面向工程设计中的各种实际问题建立优化设计模型，根据结构与力学的特点对数学规划方法进行必要的改进。因此，结构优化设计是一综合性、实用性很强的理论和技术。 目前，结构优化设计的应用领域已从航空航天扩展到船舶、桥梁、汽车、机械、水利、建筑等更广泛的工程领域，解决的问题从减轻结构重量扩展到降低应力水平、改进结构性能和提高安全寿命等更多方面。 由于结构优化设计给工程界带来了经济效益及近年来有限元研究和应用的相对成熟，计算机条件的进一步改善和普及，人们对结构优化设计的研究和应用的呼声更高了。无论国内还是国外，对这一现代技术的需求都有增长的趋势。随着设计技术的更新和产品竞争的加剧，结构优化设计将会有更大的发展。 武汉理工大学华夏学院《区域规划与城镇体系规划》结课论文 ××××× 学院（系）：土木与建筑工程系 专业班级：城规 110* 班 学生姓名：××× 指导教师：××× 目录 摘要 (181) Abstract (182) 1 绪论 (183) 1.1 ××× (183) 2 空气燃烧火焰空间的数值模拟 (183) 2.1 数值模型 (183) 参考文献 (185) 致谢 (186) 摘要 本文借助计算流体力学软件FLUENT首先针对一日产650吨的空气燃烧的燃油浮法玻璃熔窑火焰空间进行了三维数值模拟，××××××××××××××××××××××××××××××××××××××××××××××××对两种情况进行了比较，所得结果对于×××××××××××具有重要的指导意义。 论文主要研究了××××××××××××××××××××××××××××××××××××××××××××××××。 研究结果表明：××××××××××××××××××××××××××××××××××××××××××××××××。 ××××××××××××××××××××××××××××××××××××××××××××××××。 本文的特色在于：××××××××××××××××××××××××××××××××××××××××××××××××。 关键词：××××；×××；××××；×× Abstract This paper first simulates the combustion space of a 650t/day air-fuel combustion float glass furnace.Then transform it into a oxy-fuel one with the model and compare them. The results have important guiding significance in transforming float glass furnace from air-fuel to oxy-fuel combustion. ××××××××××××××××××××××××××××××××××××××××. ××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××. Key W ords：×××××；××××；numerical simulation；air-fuel combustion 《算法分析与设计》 课程实验 专业年级：信息与计算科学 学生学号： 学生姓名： 实验题目：用贪婪法求解背包问题 指导老师： 实验时间：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 武汉理工大学 算法设计与分析论文题目：贪心算法应用研究 姓名：吴兵 学院：信息工程 专业班级：电子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) 摘要 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的特点举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过贪心算法的特点来解决。 关键词：贪心算法最小生成树多处最优服务次序问题删数问题 优化设计小论文 机械优化设计 优化设计是20世纪60年代初发展起来的一门新的学科,也是一项新的设计技术。它是将数学规划理论与计算技术应用于设计领域, 按照预定的设计目标,以电子计算机及计算程序作为设计手段,寻求最优设计方案的有关参数,从而获 得较好的技术经济效益。机械的研究和应用具有悠久的历史,它伴随甚至推动了人类社会和人类文明的发展。机构学研究源远流长, 但从古到今,机构学领域主要研究三个核心问题, 即机构的构型原理与新机构的发明创造、机构分析与设 计的运动学与动力学性能评价指标、根据性能评价指标分析和设计机构。机构 是组成机械的基本单元,一般机械都是由一个或多个机构组成。对于机构的研究, 能够为发明、创造新机械提供理论、资料和经验。而对于机构的优化设计, 使 机构具有确定的几何尺寸,能够满足运动学要求, 并能实现给定的运动规律,这 些能够为某些具体的机械设计, 使机械满足某些特定的功能提供了可靠的依 据。 机械设计是机械工程的重要组成部分，是决定机械性能最主要的因素。从 工程设计基础和目标上可将设计分为：新型设计(开发性设计)、继承设计、变 型设计(基于标准型的修改)。所谓新型设计，即应用成熟的科学技术或经过实 验证明可行的新技术，设计未曾有过的新型机械，主要包括功能设计和结构设计，是机械设计发展的方向所在，然而贯穿其中的关键环节即是设计的方法和 实现的手段。人类一直都在不断探索新方法和新设计理念。从17 世纪前形成的直觉设计过渡到经验设计和传统设计，直到目前的现代设计[1]，从静态、经验、手工式的‘安全寿命可行设计’方法发展到动态、科学、计算机化、自动化的 优化设计方法，已将科学领域内的实用方法论应用于工程设计中了。 机械优化设计基本思路是在保证基本机械性能的基础上，借助计算机，应 用一些精度较高的力学/ 数学规划方法进行分析计算，让某项机械设计在规定 的各种设计限制条件下，优选设计参数，使某项或几项设计指标（外观、形状、结构、重量、成本、承载能力、动力特性等）获得最优值。 贪心算法的应用 课程名称：算法设计与分析 院系：计算机科学与信息工程学院 学生姓名：**** 学号：********** 专业班级：********************************** 指导教师：****** 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 引言 随着科学的发展，人们生活中面临的大数据量越来越多。生活的快节奏要求人们对这些庞大的数据进行简单快速的处理，在这种实际需求的背景下，计算机算法设计得到了飞速发展，线性规划、动态规划、贪心策略等一系列运筹学模型越来越多被应用到计算机算法学中。 当一个问题具有最优子结构性质和贪心选择性质时，可用动态规划法来解决。但是贪心算法通常会给出一个更简单、直观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解，而且所给出的算法一般比动态规划算法更加简单、直观和高效[1]。 2 贪心算法 2.1 贪心算法概述 贪心算法又称贪婪算法，是指在求解问题时，总是做出在当前看来是最好的选择，也就是说，贪心算法并不要求从整体上最优考虑，它所作的仅是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。贪心算法并不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。 贪心算法可以简单描述为：对一组数据进行排序，找出最小值，进行处理，再找出最小值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。 贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准 《机械创新设计》 结课论文 课程名称《机械创新设计》 院（系、部、中心）机械工程学院 专业过程装备与控制工程 班级过程装备121 姓名 XXX 学号 201121221 题目便携式笔记本电脑桌的创新设计 起止日期 2015-5-27~2015-6-22 任课教师 XXX 便携式笔记本电脑桌的创新设计 作者：XXX （南京工程学院机械工程学院，南京211167） 摘要：当前的笔记本电脑桌普遍为平板四肢式，虽然用起来小巧方便，但是仅限于室内使用，便携性差。为解决这一问题，笔者引入“折叠”元素，结合手提箱的构造，对现有电脑桌进行改进，使之既能满足便携要求，又能作为电脑包使用。大大提高了笔记本电脑桌的实用性。 关键词：电脑桌改进；折叠；手提箱；电脑包 1引言 笔记本电脑桌，简单地讲就是可以在多个场合（床上，沙发上，腿上，桌子上，阳台上）放置笔记本电脑并使用的一种多功能小桌子。 笔记本电脑桌现在市面上主要以ABS塑胶、实木和多层板几种材质为主，目前多数的塑料外壳笔记本电脑都是采用ABS工程塑料做原料的。采用新ABS工程塑料好处有，做工精细、坚固耐用、抗拉抗压、不老化、永不褪色，重量仅仅为普通木质电脑桌重量的1/4，避免了家具的的笨重。实木的又以橡胶木为高档产品，配合家装颜色材质，但其缺点是处理不好容易变形；而多层板就解决了变形问题，但买要买品牌的，因为多层板多用含有甲醛的胶。 学生族使用的笔记本电脑桌以平板四肢式为主，它造型小巧，又很实用，而且价格不高，深受学生的喜爱，如图1所示。 图1 平板四肢式笔记本电脑桌 折叠元素很常见,并作为一个自然法则早已存在于自然界中。但是在设计领域,“折叠”一词,往往是指上升到哲学层面上的“折叠”概念。哲学家就是通过揭示隐藏的自然法则,对其进行高度地凝练和概括,才创造出哲学层面上的“折叠”概念的。哲学家创造了概念,把折叠带到了一个全新的高度,而设计师们则纷纷从他们那里汲取营养。其中德勒兹的折叠概念是其哲学体系中的核心之一,并最初引申于莱布尼兹的“单子论”。折叠在现代设计领域发挥着重要作用。 2 笔记本电脑桌造型与功能概况 笔记本电脑桌按功能来分主要有以下几类： 1、可折叠。折叠起来后大小只有14寸笔记本电脑大小，方便节省空间。 2、可升降。对于不同身材的人都可以舒适的使用，这已经成为现在笔记本电脑桌的一大特色。 3、散热性。笔记本电脑桌因为是于笔记本电脑接触最多的产品，故散热功能也变为主流。常见的散热主要是由散热孔来完成。当然也有的产品加装了散热风扇，通过从笔记本的usb接口取电，来达到散热的目的。 如图2.1、图2.2、图2.3所示。 算法分析与设计实验报告 第 4 次实验 } 附录：完整代码 #include #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 算法设计与分析实验报告 题目：贪心算法背包问题 专业：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("背包问题"); SCIENTIST 33 计算机自诞生以来，发展迅速，在社会中的各个领域都得到了广泛的应用。使用计算机快速处理问题成为当今社会发展的需要。笔者运用计算机知识为现实问题提供一些意见和建议。笔者在今年“双十一”期间亲身经历了爆仓问题，发现物体配送效率低下，“双十一”期间物流速度极慢，形式十分严峻。据官方所提供的数据，买家每秒创建订单数额达到17.5万笔，有些货物甚至预计 需要1个月左右的时间才能配送完毕。 对于现今的物流配送，人们大多选择第三方物流。当货物运送到某地区时，物流公司的将货物囤积在一处，再通过快递员将快递送往千家万户。笔者在此希望对快递员的派送路线进行合理化选择，以最短路程，最小时间完成货物的配送。 以城市中的快递配送为例，现简化模型如下：快递员在某地区配送快递，快递公司（货物囤积地）位于O 点，快递员需要派送6份快递，分别送往A，B，C，D，E，F 六个地点，每两个地点之间的距离已标出，快递员如 何快速规划路线，以最短路径、最小时间完成快递的配送，这不仅可以节约劳动力提高工作效率，也会使网购用户收货速度更快。 图1 在具体代码实现中配送需求地映射为编号：O—0， A—1，B—2，C—3，D—4，E—5，F—6； 城市之间的距离用二维数组来表示，记为D[i][j]，如：D[0][1]表示O 与A 之间的距离，于是D[0][1]=6；设置flag[][]，初始为0，表示此变量未被访问（配送需求地未到达过），若被访问（已到达过配送完毕）则修改为1。 本文中笔者选择贪心算法、动态规划法来解决这一实际问题。 1 贪心算法 贪心算法（Greedy algorithm）是一种对某些动态规划中求优秀解的简单、迅速的算法，以当前情况为基础根据某个标准作最优选择，而不考虑整体情况，省去大量时间。 贪心算法在解决问题的策略上缺点是目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心算法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。但由于其处理问题简单高效、节省空间，非常适合实际问题的解决。 现在我们通过来解决这一问题，采用最近邻点策略：从某地点（初始为快递公司，即O 点）出发，每次在没有到过的中选择距离当前所在地中最近的一个，直到经过了所有的配送需求地，完成了所有配送任务，最后回到快递公司，即O 点。 贪心算法具体求解流程如下：1）了解要求送达地点的的数量与各地点之间的距离。2）重复以下两步直至已全部送达：（1）循环遍历找到与当前出发地点最近的未到达过的配送需求地；（2）以当前找到的（最近一次找到的）送达地点为出发地点，重复步骤（1）。3）回到出发地点。 在本题中贪心算法选择路线经过如下：快递员从O 点选择较近的A 点作为目的地。到达后选择距离当前出发点A 较近的点，O 点当前已访问，选择B 点。而后依次按照此规则选择配送需求点，当所有快递配送完毕返回O 点，即快递公司所在地。路线为O->A->B->C->D->E->F->O。路程为44。 从本例中也可以看出，贪心算法简单便捷，对于问题的解决有很大的帮助。同时我们清楚地看出，使用贪心算法只能考虑当前的选择，当面对复杂的整体问题 物流配送问题中贪心算法与动态规划法的分析与应用 徐西啸 山东省莱芜市第一中学，山东莱芜 271100 摘 要 计算机的应用触及到了生活的各个方面，它的优点之一就在于强大的计算处理能力上，这也正是物流领 域配送路线的问题所需要的。如何选择最佳路线，如何节约物流运输成本，即选择配送的最短路线，我们可以通过贪心算法和动态规划算法来做决定。本文对于中国现今发展蓬勃的电子商务的线下运输问题提出了见解，以一个简化的模型介绍了贪心算法以及动态规划法的应用，为线下运输问题提出了解决方案，有着十分重要的现实意义。关键词 物流问题；最短路径；最小时间；贪心算法；动态规划 中图分类号 TP3 文献标识码 A 文章编号 2095-6363（2016）18-0033-02 作者简介：徐西啸，山东省莱芜市第一中学。 生物学案的优化设计 沈后方（江苏省盱眙县实验中学 211700） 摘要：本文以生物教学中学案设计优化设计的背景和意义为出发点，阐述生物教学中学案的优化设计的具体做法。使学案发挥更大的作用。 关键词：生物学案优化设计 学案，是指教师依据学生的认知水平,知识经验，为指导学生进行主动的知识建构而编制的学习方案。教师用以帮助学生掌握教材内容，沟通学与教的桥梁，能够提高学生课堂学习效率。 1、生物学案的布局优化 传统的学案往往只注重内容而不注重布局，如能在布局上加以优化，会收到良好的效果。首先是页眉、页脚的设计，常规学案在页眉部分的信息包括学校、年级、编号和日期等；页脚部分一般是作为页码设置。但在设计生物学案时可以进一步挖掘此区域的功能，充分发挥此信息区的作用，在页眉可根据本章节的内容设计一些简短小常识，如“环境保护日”、“辣椒含大量维生素被称为V c之王”、等等。在页脚可以设计一段小笑话以缓解学生学习的疲劳。 2、生物学案的内容优化 学案可以在内容上更加多样化，传统的学案说白了就是教师印发给学生的习题训练。缺乏知识性、趣味性、系统性和开放性。学生做起来及其枯燥。如能在内容及其形式上加以优化，会给学生耳目一新的感觉，增强学习的趣味性。总体内容可以涵盖以下几个方面：1、教学目标；2、知识网络；3、习题训练；4、知识 拓展；5、信息反馈。 首先，目标明确。在明确的目标指引下来了解知识网络，形成知识体系。即知识网络，可以采用概念图的形式或以图表形式展示，形象生动、一目了然。 其次，习题训练。题型要多样，题量要精简。把空间留出来给知识拓展，专门开辟一块知识阅读的版块，如：记述生物名人小故事、介绍形形色色的动物和植物、当代生物科学研究前沿信息等等。 最后，还要给学生留出篇幅抒发感慨和想象的空间，或者提出一两个小小的思考题激发学生的思维。较好保证学案的效果。 3、生物学案的提示语的优化 提示语是用来提醒人们注意自己行为、语言的一些语句。脍炙人口、富有品味的提示语能让人们在潜移默化中受到启迪。同样，在教学案的各给模块中穿插一些温馨的提示语，可以增强学生的认同感，拉近师生之间的距离。 实践表明，优化后的学案设计改变了以往传统的学案的枯燥和浪费。使空间得到了高效的利用。同时，使学生有以前对学案的态度的由害怕变为了期盼。使他们在真正学到了知识同时，也享受了快乐。 主要参考文献 [1]束爱军蒋选荣.2011.优化作业纸的设计.生物学教学，36(10):30-31。 算法设计与分析大作业 班级：电子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页 贪心算法详解 贪心算法思想： 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本要素： 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 用背包问题来介绍贪心算法： 背包问题：有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要 求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 现代机械优化设计 摘要：机械优化设计是近年来发展起来的一门新的学科，起始于20世纪60年代，非常有发展潜力的研究方向，是解决复杂设计问题的一种有效工具。在机械应用的实践中，机械优化设计是一种非常重要的现代设计方法，能从众多的设计方案中找出最佳方案，从而大大提高设计的效率和质量 关键词：优化设计；方法特点；发展态势 一、机械优化设计的设计思想 机械优化设计是为了适应于不断发展的生产现代化而发展起来的。它建立在数学规划理论和计算机程序设计基础上，通过有效的实验数据和科学的评价体系来从众多的设计方案中寻到尽可能完善的或最适宜的设计方案。该领域的研究和应用进展非常迅速，并且取得了可观的经济效益。 所谓优化设计就是在规定的各种设计限制条件下，将实际设计问题首先转为最优化问题，然后运用最优化理论和方法，在电子计算机上进行自动调优计算，从满足各种设计要求及限制条件的全部可行方案中，选定出最优设计方案。就最优化的理论和方法而言，继古典的微分法和变分法之后，出现有数学规划优化法、准则优化法、混合法及利用遗传算法、人工神经网络的优化方法等。进入21世纪，工程技术人员普及应用最优化方法是必然趋势 1．设计变量 设计变量是指在设计过程中我们必须全面考虑确定的各项独立参数，一旦这些设计参数全部确定了，设计方案也就完全确定了。他们在整个设计过程中相当于一个个变量，变量的多少与数值大小直接影响着优化工作的复杂程度。也就是说，设计变量数目越多，设计空间的维数越大，优化设计工作也就越复杂，同时效益也越显著。因此在选择设计变量时。必须兼顾优化效果的显著性和优化过程的复杂性。 2．约束条件 约束条件是设计变量间或设计变量本身应该遵循的限制条件，而优化设计问题大多数是约束的优化问题。针对优化设计数学模型要素的不同情况，可将优化设计方法进行分类。约束条件的形式有显约束和隐约束两种，前者是对某个或某组设计变量的直接限制，后者则是对某个或某组设计变量的间接限制。等式约束对设计变量的约束严格，起着降低设计变量自由度的作用。优化设计的过程就是在设计变量的允许范围内，找出一组优化的设计变量值，使得目标函数达到最优值。 3．目标函数 在优化设计过程中，每一个变量之间都存在着一定的相互关系这就是用目标函数来反映。他可以直接用来评价方案的好坏。在优化设计中，可以根据变量的多寡将优化设计分为单目标优化问题和多目标优化问题，而我们最常见的就是多目标函数优化。 一般而言，目标函数越多，设计的综合效果越好，但问题求解越复杂。在实际的设计问题中，常常会遇到在多目标函数的某些目标之间存在矛盾的情况，这就要求设计者正确处理各目标函数之间的关系。对这类多目标函数的优化问题的研究，至今还没有单目标函数那样成熟。 二、机械优化设计的主要特点 在优化设计过程中，每一种优化方法都是针对某一种问题而产生的，都有各自的特点和贪心算法0-1背包问题(算法实验代码)
贪心算法经典例题
结构优化设计论文
结课论文格式——3000字左右
算法设计实验_贪心算法背包问题
算法分析与设计选修课-贪心算法应用研究
优化设计小论文
【精选】贪心算法的应用
贪心算法结课论文
机械创新设计结课论文
背包问题(贪心算法)
C语言版贪心算法背包问题
贪心算法背包问题
物流配送问题中贪心算法与动态规划法的分析与应用
教学案的优化设计(论文)
0-1背包问题的算法设计策略对比与讲解
贪心算法详解分析
【精品毕设】现代机械优化设计课程论文
相关主题
文本预览