下载文档原格式
10算法策略之贪婪法贪婪算法贪婪法⼜叫登⼭法, 它的根本思想是逐步到达⼭顶,即逐步获得最优解。
贪婪算法没有固定的算法框架，算法设计的关键是贪婪策略的选择。
⼀定要注意，选择的贪婪策略要具有⽆后向性。
某状态以后的过程和不会影响以前的状态,只与当前状态或以前的状态有关,称这种特性为⽆后效性。
可绝对贪婪问题【例1】键盘输⼊⼀个⾼精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成⼀个新的正整数。
编程对给定的N和S，寻找⼀种⽅案使得剩下的数字组成的新数最⼩。
输⼊数据均不需判错。
输出应包括所去掉的数字的位置和组成的新的正整数（N不超过240位）。
数据结构设计：对⾼精度正整数的运算在上⼀节我们刚刚接触过，和那⾥⼀样，将输⼊的⾼精度数存储为字符串格式。
根据输出要求设置数组，在删除数字时记录其位置。
我们采⽤⽅法1）。
⼀种简单的控制相邻数字⽐较的⽅法是每次从头开始，最多删除s次，也就从头⽐较s次。
按题⽬要求设置数组data记录删除的数字所在位置。
较s次。
按题⽬要求设置数组data记录删除的数字所在位置delete(char n[],int b,int k){int i;for(i=b;i<= length(n)-k;i=i+1) n[i]=n[i+k];}main（）{char n[100]; int s,i,j,j1,c,data[100],len;input(n); input(s); len=length(n);if(s>len){print(“data error”); return;}j1=0;for (i=1;i<=s ;i=i+1){for (j=1;j<length(n);j=j+1)if (n[j]>n[j+1]) //贪婪选择{delete(n,j,1);if (j>j1) data[i]=j+i; //记录删除数字位置else //实例2向前删除的情况实例data[i]=data[i-1]-1;j1=j; break; }if( j>length(n)) break;}for (i=i;i<=s;i=i+1){ j=len-i+1;delete(n,j,1); data[i]=j;}while (n[1]='0' and length(n) >1)delete(n,1,1); //将字符串⾸的若⼲个“0”去掉 print(n);for (i=1;i<=s;i=i+1)print(data[i],' ');}算法说明1：注意记录删除位置不⼀定是要删除数字d的下标，因为有可能d的前或后有可能已经有字符被删除，d的前⾯已经有元素删除容易想到，但⼀定不要忽略了其后也有可能已删除了字符，实例2中删除1时，其后的2已被删除。
贪婪算法在资源分配问题中的应用彭鹏贵州财经学院研究生摘要：贪婪算法的典型应用是解决优化问题，这类算法的策略是只顾眼前，而不考虑以后的影响，它的算法简单容易设计实现，因此在许多实际问题中得到广泛的应用，但是它也存在许多的问题，巧妙的使用贪婪思想，将其融入到资源分配问题中解题中，资源分配问题便焕发出了新的光彩。
本文首先对贪婪算法的基本概念做了介绍，然后通过实例论述了贪婪算法在资源分配问题中的应用。
关键字：贪婪算法研究应用资源分配问题第一章贪婪算法的概念1.1什么是贪婪算法贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。
用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。
贪婪算法是一种改进了的分级处理方法。
其核心是根据题意选取一种量度标准。
然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。
如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。
这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。
对于一个给定的问题，往往可能有好几种量度标准。
初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。
因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。
一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。
最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。
c语言算法--贪婪算法---0/1背包问题在0 / 1背包问题中，需对容量为c 的背包进行装载。
从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。
对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即n ?i=1pi xi 取得最大值。
约束条件为n ?i =1wi xi≤c 和xi?[ 0 , 1 ] ( 1≤i≤n)。
在这个表达式中，需求出xt 的值。
xi = 1表示物品i 装入背包中，xi =0 表示物品i 不装入背包。
0 / 1背包问题是一个一般化的货箱装载问题，即每个货箱所获得的价值不同。
货箱装载问题转化为背包问题的形式为：船作为背包，货箱作为可装入背包的物品。
例1-8 在杂货店比赛中你获得了第一名，奖品是一车免费杂货。
店中有n 种不同的货物。
规则规定从每种货物中最多只能拿一件，车子的容量为c，物品i 需占用wi 的空间，价值为pi 。
你的目标是使车中装载的物品价值最大。
当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。
这个问题可仿照0 / 1背包问题进行建模，其中车对应于背包，货物对应于物品。
0 / 1背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入。
在每一步过程中利用贪婪准则选择一个物品装入背包。
一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。
这种策略不能保证得到最优解。
例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 1 0 5。
当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。
而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。
另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。
贪心法贪心法(Greedy Approach)又称贪婪法, 在对问题求解时，总是做出在当前看来是最好的选择，或者说是：总是作出在当前看来最好的选择。
也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
当然，希望贪心算法得到的最终结果也是整体最优的。
虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。
如单源最短路经问题，最小生成树问题等。
在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
贪心法的设计思想当一个问题具有以下的性质时可以用贪心算法求解:每一步的局部最优解，同事也说整个问题的最优解。
如果一个问题可以用贪心算法解决，那么贪心通常是解决这个问题的最好的方法。
贪婪算法一般比其他方法例如动态规划更有效。
但是贪婪算法不能总是被应用。
例如，部分背包问题可以使用贪心解决，但是不能解决0-1背包问题。
贪婪算法有时也用用来得到一个近似优化问题。
例如，旅行商问题是一个NP难问题。
贪婪选择这个问题是选择最近的并且从当前城市每一步。
这个解决方案并不总是产生最好的最优解，但可以用来得到一个近似最优解。
让我们考虑一下任务选择的贪婪算法的问题, 作为我们的第一个例子。
问题：给出n个任务和每个任务的开始和结束时间。
找出可以完成的任务的最大数量，在同一时刻只能做一个任务。
例子:下面的6个任务：start[] = {1, 3, 0, 5, 8, 5};finish[] = {2, 4, 6, 7, 9, 9};最多可完成的任务是：{0, 1, 3, 4}贪婪的选择是总是选择下一个任务的完成时间至少在剩下的任务和开始时间大于或等于以前选择任务的完成时间。
我们可以根据他们的任务完成时间，以便我们总是认为下一个任务是最小完成时间的任务。
1)按照完成时间对任务排序2)选择第一个任务排序数组元素和打印。
3) 继续以下剩余的任务排序数组。
……a)如果这一任务的开始时间大于先前选择任务的完成时间然后选择这个任务和打印。
组合优化问题的算法与求解组合优化问题是一类需要在给定的约束条件下找到最优解的问题。
这些问题在现实生活中有着广泛的应用，比如物流配送问题、旅行商问题等等。
本文将介绍几种常见的组合优化问题的算法以及它们的求解方法。
一、贪婪算法贪婪算法是一种简单而高效的求解组合优化问题的方法。
它通过在每一步选择当前看起来最优的解决方案，逐步建立起最终的解。
贪婪算法通常具有快速的执行速度和较好的近似解质量。
例如，对于旅行商问题，贪婪算法可以从一个起点开始，每次选择离当前位置最近的未访问节点作为下一个访问节点，直到所有节点都被访问过。
这样，贪婪算法可以得到一个近似的最短路径。
二、回溯算法回溯算法是一种穷举搜索的方法，它通过逐个尝试所有可能的解决方案，并逐步剪枝以减少搜索空间。
回溯算法通常适用于组合优化问题的求解，尤其是在问题规模较小的情况下。
以0-1背包问题为例，回溯算法可以通过穷举所有可能的物品选择方式，计算其总价值，并在搜索过程中剪枝以提高效率。
回溯算法的优势在于能够找到最优解，但在问题规模较大时，耗时较长。
三、动态规划算法动态规划算法是一种将问题分解为子问题并记录子问题结果的方法。
它适用于能够将原问题分解为相互重叠的子问题，并利用子问题的解来推导原问题的解。
比如在背包问题中，动态规划算法可以通过定义状态转移方程来解决。
设dp[i][j]表示在前i个物品中选择总重量不超过j的情况下的最大价值，则有以下状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])通过填表计算，可以获得最终的最优解。
四、遗传算法遗传算法是一种模拟自然选择和遗传机制的搜索算法。
它通过模拟生物种群的遗传、变异、选择等过程，逐步演化出最优解。
遗传算法在求解组合优化问题时，通过编码将解空间中的解表示成染色体，并利用交叉、变异等遗传操作来搜索更优的解。
通过不断迭代，遗传算法能够找到较好的解，但无法保证找到全局最优解。
贪婪取走启发式算法贪婪算法是一种启发式算法，用于解决优化问题。
该算法通常采取一种贪心的策略，在每一步选择中都做出局部最优的选择，迭代执行，直到达到全局最优解或近似最优解。
贪婪算法的主要优势在于其高效性和简单性。
贪婪算法的思想是利用局部最优解推导出全局最优解。
这意味着每一步都采取最优的选择，而无需考虑将来的影响。
虽然贪婪算法可能不能保证获得全局最优解，但通常可以获得一个接近全局最优解的近似解。
贪婪算法有很多应用。
以下是几个常见的例子：1.零钱找零问题：给定一定面额的硬币和要找零的金额，目标是找到最少的硬币数来凑够找零金额。
贪婪算法的策略是在每一步中选择最大的硬币，直到找零金额为零。
2.最小生成树问题：给定一个带权重的无向连通图，目标是找到具有最小总权重的生成树。
贪婪算法的策略是从任意节点开始，每次选择连接最小权重的边，直到所有节点都被连接为止。
3.背包问题：给定一定容量的背包和一组物品，每个物品有自己的重量和价值。
目标是在不超过背包容量的前提下，选择物品使得总价值最大化。
贪婪算法的策略是计算每个物品的单位价值，选择单位价值最高的物品，直到背包容量用尽。
贪婪算法的优点是简单和高效。
它通常对于大规模问题提供了接近最优的解决方案。
然而，这种算法也有其局限性。
因为贪婪算法只考虑当前步骤的最优解，而不考虑将来的影响，所以它可能无法找到全局最优解。
在一些问题中，贪婪算法可能会陷入局部最优解，因此无法得到最优的结果。
总结而言，贪婪算法是一种简单而高效的启发式算法。
它通过每一步选择局部最优解，迭代执行，以获得全局最优解或近似最优解。
贪婪算法在许多优化问题中都有应用，但是它也有一些局限性。
要使用贪婪算法，需要权衡问题的特征和目标，以确定它是否适合解决该问题。
贪婪算法在NP完全问题中的应用NP完全问题是计算机科学中的一个非常重要的概念。
解决 NP 完全问题是一个集体智慧和计算机科学领域的挑战。
要想解决 NP 完全问题，我们必须依靠复杂的算法和工具，以找到最优解或者近似解。
在这些算法当中，贪婪算法是一个非常优秀的解决方案。
什么是 NP 完全问题？首先，让我们来回顾一下 NP 完全问题的定义。
NP 完全问题是指那些可以在多项式时间复杂度内验证一个解是正确的，但是无法在多项式时间内找到最优解的问题。
例如，旅行商问题、背包问题等等。
为什么 NP 完全问题如此难解？NP 完全问题如此难解，是因为它们的解决方案非常依赖于问题大小。
也就是说，随着问题的大小不断增加，问题的解决时间也会呈指数级增长。
换句话说，寻找最优解可能需要非常长的时间。
例如，对于旅行商问题，只有通过计算所有可能的路线才能找到最短路径。
贪婪算法介绍贪婪算法是一种解决问题的算法，能够在较短的时间内找到问题的近似最优解。
这种算法的基本思想是在每一步中，以当前状态为基础，每次选择最优解，直到达到全局最优解。
贪婪算法通常简单、高效、易于理解和实现。
使用贪婪算法解决背包问题背包问题是一个典型的 NP 完全问题。
它是指有一个背包，可以装载一些重量不等、价值不同的物品。
现在我们需要选择一些物品放入背包，使得背包中最终装下的物品价值最高。
在使用贪婪算法解决背包问题时，我们以物品的价值作为排序的依据，每次选择价值最高的物品放入背包中。
在这个过程中，我们需要根据背包的容量对物品进行分类，以避免选择哪些不能装入背包的物品。
通过这种方法，我们可以在短时间内找到一个近似最优解。
虽然贪婪算法可以在较短时间内找到问题的近似最优解，但是它并不总是找到全局最优解。
这也是贪婪算法的一个缺点。
但是，贪婪算法在实际应用中仍然具有很高的价值。
通过使用贪婪算法，我们可以解决许多实际问题，如路由问题、图形问题、网络流等等。
结论贪婪算法是解决 NP 完全问题的一种非常好的算法。
