贪心算法的应用
课程名称：**************
院系：************************
学生姓名：******
学号：************
专业班级：*****************************
指导教师：******
2013年12月27日
摘要:
贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。
一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。
关键词：贪婪算法，引索，生成最小数
目录
第1章绪论 (3)
1.1 贪婪算法的背景知识 (3)
1.2 贪婪算法应用 (3)
第2章贪婪算法的理论知识 (4)
2.1 贪婪算法的原理 (4)
2.2 如何贪婪 (4)
2.3贪婪的正确性 (4)
第3章贪婪算法的实例 (5)
3.1 问题描述 (5)
3.2 问题分析 (5)
3.3 算法设计一 (6)
3.3.1数据结构 (6)
3.3.2代码及流程图 (7)
3.3.3 截图 (10)
3.4 算法二 (11)
3.4.1 数据结构 (11)
3.4.2 程序代码及截图 (11)
3.4.3 算法二截图 (15)
3.5 运行结果分析 (15)
第5章结论 (16)
参考文献 (17)
第1章绪论
1.1 贪婪算法的背景知识
贪心思想的本质是每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。即，贪婪法建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完全解为止。这个技术的核心是，所做的每一步选择都必须满足：
1.可行的：即它必须满足问题的约束。
2.局部最优：它是当前步骤中所有可行选择中最佳的局部选择。
3.不可取消：即选择一旦做出，在算法的后面步骤中就无法改变了。
贪心算法的最大特点就是快。通常，二次方级的存储要浪费额外的空间，而且很不幸，那些空间经常得不出正解。但是，当使用贪心算法时，这些空间可以帮助算法更容易实现且更快执行。
1.2 贪婪算法应用
贪婪算法总是做出在当前看来最好的选择。也就是说贪婪算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。当然，希望贪婪算法得到的最终结果也是整体最优的。虽然贪婪算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。在一些情况下，即使贪婪算法不能得到整体最优解，其最终结果却是最优解的很好近似。
如果需要解决的问题有贪婪性质存在，那么采用贪婪算法无疑是最好的选择！因为基于贪婪算法的程序执行起来速度极快，并且节约空间。衡量算法的关键就是效率，即程序执行时消耗的时间和空间。当然，贪心算法有一定使用范围，而且有一部分极难证明，若是没有把握，最好还是不要冒险，因为还有其他算法会比它要保险。
第2章贪婪算法的理论知识
2.1 贪婪算法的原理
所谓贪婪算法指的是为了解决在不回溯的前提之下，找出整体最优或者接近最优解的这样一种类型的问题而设计出来的算法。贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质：1.整体的最优解可以通过局部的最优解来求出；2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。
2.2 如何贪婪
怎样才能从众多可行解中找到最优解呢？其实，大部分都是有规律的。在样例中，贪婪就有很明显的规律。在每一步中，它要求“贪婪”地选择最佳操作，并希望通过一系列局部的最优选择，能够产生一个整个问题的(全局)最优解。正因为贪心有如此性质，它才能比其他算法要快。然而，还有一些问题并不是这种情况，对于这样的问题，如果我们关心的是，或者说我们能够满足于一个近似解，贪婪算法仍然是有价值的。
2.3贪婪的正确性
要证明所设计贪婪方法的正确性，才是真正挑战，因为并不是每次局部最优解都会与整体最优解之间有联系，往往靠贪婪方法生成的解不是最优解。这样，贪婪方法的证明就成了贪婪正确的关键。一个你想出的贪婪方法也许是错的，即使它在大部分数据中都是可行的，你必须考虑到所有可能出现的特殊情况，并证明你的贪婪方法在这些特殊情况中仍然正确。这样经过千锤百炼的性质才能构成一个正确的贪婪方法。
第3章贪婪算法的实例
3.1 问题描述
键盘输入一个高精度的正整数n，去掉其中任意s个数字后剩下的数字按照原来的左右次序将组成一个新的正整数。编写程序对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。输应出包括去掉的数字的位置，和组成的新数的正整数（n不超过240位）。
3.2 问题分析
在位数固定的前提下，让高位的数字尽量小，其值就较小，依据此贪婪策略就可以找到解决问题的方案。关于贪心算法的可行性证明如下：
对于一个n位数字，任意去掉其中一位数字，保持其余数字的左右顺序不变，要使生成的新数最小，则应该从最高位开始向低位查找，找到第一个比低位数大的数字去掉即可。
即，对于正整数n = abcde, 从最高位向低位查找，找到第一位比下一位数字大的数，假定为c，即（a
若保留c，则有两种情况：其一，去掉c之前的数（a或b），则形成的新数为：x11 = a*1000+c*100+c*10+e，或x12 = b*1000+c*100+d*10+e，很显然,由于c
如n = 12435时，去掉的一位，应该是4，形成新数为1235。若去掉的不是4，则只有两种情况，其一，去掉1或2，则形成的新数中4变成了第二高位，自然不如去掉4小；其二，去掉3或5，则4变成了第三高位，不如去掉4时小。之前讨论的是n位数去掉其中1位后形成的新数最小，而题目要求是去掉其中s 为数后形成的新数最小。所以需要重复去掉s次一位数就实现了题目的要求。
当然，不能遗漏了一些特殊情况，如1234去掉s=2时，按照以上算法无法解决，由于数字本身就按顺序排列，故应从后先前去掉s位即可；又如1023去掉s=1位后变成了023，此时需要将0首位为0的数字也去掉；再如1000去掉s= 1后变成了000，将首位为0的数字去掉时需考虑是否将三个0全去掉了，这样就不会显示结果了，因此须保留一位0。
3.3 算法设计一
经以上分析，对于本题采用贪婪算法解决。将整个程序分为4部分：初始化，一般情况的处理，处理特殊情况，输出结果。
一般情况的处理。即，用一个循环（s次）每次循环从最高位开始向低位查找，直到找到一个比下一位大的数字然后删除，或者找不到这样的数字然后跳出循环，结束一般情况的处理。
处理特殊情况。需要处理上一部删除不到s位的情况：从末位先前删除直到删除够s位数字；还需要处理删除s位数字后形成新数的首位为0的情况：将首位为0的数字删除首位；处理删除s后剩余数字全部为0的情况：需要将所有多余的0删除，剩下一个0表示结果即可。
3.3.1数据结构
由于要存储的数字为高精度正整数，之后还需要逐个进行比较，因此用char[]或int[]类型的数组存储会更好些，本算法采用的是char[]类型变量n；另一个int[]类型的辅助变量index，尽管index为辅助变量，却起着很大的作用：
(1).初始状态（未有数字删除）。index[i]表示n[i]的上一个数字的下标，初始化为i-1，此时index[i] < I;
(2).删除后，当n[i]被删除后Index[i]表示n[i-1]个数的下一个数的下标，此时index[i] > i;
(3).输出结果。在输出删除的数字下标，和删除s个数字后剩余的数字组成的新数时，可以仅判断index[i]和i的大小即可，index[i] > i时，表示该数字已删除，下标i即是被删除数字的位置；index[i]< i时，表明该数字未删除。
(4).index的最大作用便是引索。在对数组进行遍历的时候，访问n[i]时需
先比较一下index[i] 与I 的大小，若index[i] > i则该数字已被删除，无需访问，可直接跳到 I = index[i] 的位置，这一跳可能从i= 1跳到i= 2，也可能从i= 1 跳到了i= 100，因此index的引索作用可使程序的效率大大提高。
3.3.2代码及流程图
#include
using namespace std;
void output(char * n, int * index, int len);
void main(){
char n[20];//高精度数
int i = 0, j = 0, s, index[20];//保存上一个数字下标
cout<<" n = ";
cin >> n;
cout<<"s = ";
cin>>s;
int len = 0;
while(n[len] != 0)//数字的位数
len ++;
if(s > len)
cout<<"data error"< else if(s == len) cout<<"0"< else{ for(i = 0; i <= len; i ++){//初始化index index[i] = i - 1; } int t; while(s != 0){ j = index[0] == -1 ? 0: index[0];//第一个数字 for(; j < len - 1; j = t){ //遍历数组逐个比较判断是否删除t = j +1; while(index[t] > t) t = index[t]; if(n[j] > n[t]){ //若n[j]比n[j+1]大 index[t] = index[j]; //将j+1个数的数的引索改为index[j]; index[j] = t; //将该值 s--; break; } } if( j == len-1) break; } for(i = len - 1; s != 0; s --){//从末位开始向前继续删除s个数 j = index[i]; index[i] = len; i = j; } i = index[0] == -1 ? 0: index[0];//第一个数字 while(n[i] == '0'&& i < len){//若第一个数字为0，且未越界 index[0] = i++; i = index[i] > i ? index[i] : i;//寻找下一个可作为第一个数字的数 } if(i < len) //若存在不等0 的数，将其作为第一个数 index[0] = i; output(n,index, len); } } void output(char * n, int * index, int len){ cout<<" n = "; int i; for(i = 0; i < len;){ if(index[i] > i) i = index[i]; else cout<< n[i++]; } cout< if(index[0] > 0 && n[0] != '0') cout<<"0 "; for(i = 1; i < len; i ++){ if(index[i] > i) cout< } cout< } 3.3.3 截图 图3-1算法一运行结果1 图3-2算法一运行结果2 图3-1算法一运行结果1 3.4 算法二 算法一用两层循环实现了将n位正整数删除s位后生成最小新数的功能。但每删除一个数字就得从新从头开始循环，这样的话，数字n的前边的数字尽管可能早已最优，但之后的每次循环依然需要逐个访问。因此算法的效率比较低。下面介绍一种相对高效的算法： 相对于算法一，这个算法改进之处在于，在删除一个数字之后，不是从头开始在逐个访问，查找出需要删除的项，而是从已删除的位置开始向前查找遇到需要删除的数字便删除，否则继续向后查找。如此，便减少了许多不必要的操作，从而提高算法的效率。 3.4.1 数据结构 所用的数据域与算法一基本相同。唯一不同的是index数组的作用。 char[]数组n存储数字n，int[]数组index为查找时的引索。Index在算法二中的作用比算法一多了一项：删除数字n[i]后需要向前查找时，index[i]提供需要查找的上一项的下标，即n[index[i]]即是n[i]的上一个相邻数字。 在算法二中增强了index的索引功能，从而使算法更高效。 3.4.2 程序代码及截图 #include using namespace std; void Delete(char * n, int * index, int j, int& s); void output(char * n, int * index, int len){ cout<<" n = "; int i; for(i = 0; i < len;){ if(index[i] > i) i = index[i]; else cout<< n[i++]; } cout< <<"删除的数字位置为："; if(index[0] > 0 && n[0] != '0') cout<<"0 "; for(i = 1; i < len; i ++){ if(index[i] > i) cout< } cout< } void main(){ char n[20];//高精度数 int i = 0, j = 0, s, index[20];//保存上一个数字下标 cout<<" n,s = "; cin >> n >> s; int len = 0; while(n[len] != 0)//数字的位数 len ++; if(s > len) cout<<"data error"< else if(s == len) cout<<"0"< else{ for(i = 0; i <= len; i ++){//初始化index index[i] = i - 1; } for(j = 0 ; j < len - 1; j ++){ //遍历数组逐个比较判断是否删除 if(n[j] > n[j + 1]){ //若n[j]比n[j+1]大 Delete(n,index,j, s); //则删除 if(s == 0) break; //已删除了s个数，跳出 } } for(i = len - 1; s != 0; s --){//从末位开始向前继续删除s个数 j = index[i]; index[i] = len; i = j; } i = index[0] == -1 ? 0: index[0];//第一个数字 while(n[i] == '0'&& i < len){//若第一个数字为0，且未越界 index[0] = i++; i = index[i] > i ? index[i] : i;//寻找下一个可作为第一个数字的数 } if(i < len) //若存在不等0 的数，将其作为第一个数 index[0] = i; output(n,index,len); } } void Delete(char * n, int * index, int j, int& s){//删除n中第j个数index[j + 1] = index[j]; //将j+1个数的上一个数的引索改为index[j]; index[j] = j+1; //将该值 int i =index[j+1]; while( -- s != 0 && i != -1 && n[i] > n[j+1]){ index[j+1] = index[i]; index[i] = j+1; i = index[j+1]; } } 3.4.3 算法二截图 图3-4 算法二运行结果1 图3-5 算法二运行结果2 图3-6 算法二运行结果3 3.5 运行结果分析 根据以上两种算法的运行结果可以看出，算法一二都实现了问题的解。能够处理一般情况下的高精度正整数n去掉s位后生成最小数，也能处理之前问题分析中讨论过的三种特殊情况下的实现。因此，这两个算法成功的实现了贪婪算法解决实例问题。 第5章结论 通过这次贪心算法的编程练习，帮助我们复习了图的遍历相关知识。在分析问题时，为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。 在解决此问题时，并不是一帆风顺的，首先是存储高精度正整数的数，然后选用数据结构的问题，经反复斟酌，采用char[]类型数据存储整数n，而int[]类型的辅助变量来解决删除数字后前后数字连接问题，从而使问题的解决更加高效。其次是，多种情况的分析，因为一个数字去除其中几位后可能形成多种情况的数，其中0作为首位时需将其删除，二剩余数字均为0时还要保留一个0，等多种特殊情况需要考虑，因此这次大作业带给我的收获不仅仅是学会了贪心算法，更多的是关于编程经验。 参考文献 [1] 算法设计与分析（第二版）吕国英主编 [2] 算法设计与分析张德富 [3] 数据结构严蔚敏
相关主题
文本预览