贪心算法详细讲解（附例题，一看就会）

发布时间：2024-11-26 10:36

如有问题，附带详细问题列表 #生活技巧# #沟通技巧# #邮件礼仪#

概念

贪心算法（Greedy Algorithm）又叫登山算法，它的根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但是适用范围有限的策略。
贪心算法没有固定的框架，算法设计的关键是贪婪策略的选择。贪心策略要无后向性，也就是说某状态以后的过程不会影响以前的状态，至于当前状态有关。
贪心算法是对某些求解最优解问题的最简单、最迅速的技术。某些问题的最优解可以通过一系列的最优的选择即贪心选择来达到。但局部最优并不总能获得整体最优解，但通常能获得近似最优解。
在每一部贪心选择中，只考虑当前对自己最有利的选择，而不去考虑在后面看来这种选择是否合理。

贪心算法求解事应考虑的问题

1.候选集合S
为了构造问题的解决方案，有一个候选集合C作为问题的可能解，问题的最终解均取自于候选集合C。
2.解集合S
随着贪心选择的进行，解集合不断扩展，直到构成一个满足问题的完整解。
3.解决函数solution
检查解集合是否构成问题的完整解。
4.选择函数select
即贪心策略，这是贪心算法的关键，它指出哪个候选对象有希望构成成问题的解。
5.可行函数feasible
检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。

贪心算法的基本步骤

1.从问题的某个初始解出发
2.采用循环语句，党可以向求解目标前进一步时，就根据局部最优策略，得到一个不分解，缩小问题的范围或规模。
3.将所有的部分解综合起来，得到问题的最终解。

Greedy(C){//C是问题的输入集合即候选集合S={};//初始解集合为空while(not solution(S)){//集合S没有构成问题的一个解x=select(C);//在候选集合C中做贪心选择if feasible(S,x);//判断集合加入x后的解是否可行S=S+{x};C=C-{s};}return S; } 12345678910

贪心策略选择

贪心算法的原理是通过局部最优来达到全局最优，采用的是逐步构造最优解的方法。在每个阶段，都做出一个看上去最优的，决策一旦做出，就不再更改。

要选出最优解可不是一件容易的事，要证明局部最优为全局最优，要进行数学证明，否则就不能说明为全局最优。
很多问题表面上看来用贪心算法可以找到最优解，实际上却把最优解给漏掉了。这就像现实生活中的“贪小便宜吃大亏”。所以我们在解决问题的时候，一定要谨慎使用贪心算法，一定要注意这个问题适不适合采用贪心算法。

贪心算法很多时候并不能达到全局最优，为什么我们还要使用它呢？

因为在很多大规模问题中，寻找最优解是一件相当费时耗力的事情，有时候付出大量人力物力财力后，回报并不与投入成正比。在这个时候选择相对最优的贪心算法就比较经济可行了。有的问题对最优的要求不是很高，在充分衡量付出和回报后，选择贪心算法未尝不是一种不错的选择呢。

例题

可绝对贪婪问题

问题：组成新数最小
键盘输入一个高精度(数字比较大)的正整数n，去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。对于给定的n和s，通过编程寻找一种方案使得剩下的数字组成的新数最小。
输出应包括所去掉的数字的位置和组成的新的正整数（n不超过240位）.
思路：
数据结构设计：因为输入的数字比较大，将输入的数字存储为字符串格式，在删除时记录删除的位置。
问题分析：
让高位的数字尽量小，数字的总值就小。

从高位到低位，让相邻的数字进行比较（总是让左边数字的与右边的数字比较），如果高位的数字比低位大，就把高位删除。

如果比较过后删除了高位，那么将低位与删除的高位的左边数字进行比较，如果高位数字大，把高位删除(即删除i位后，必须向前考虑i-1位与第i+1位进行比较)。

例如
n=“2 3 1 1 8 3”
3比1大删除：“2 空 1 1 8 3”
2比1大删除：“空空 1 1 8 3”
8比3大删除：“空空 1 1 空 3”
即删除i位后，必须向前考虑i-1位与第i+1位进行比较

如果前面高位出现0（例如003），则不合理，应该把前面的0都删掉。

如果数字全是0，应该保留一个零。（下面的代码中没有考虑到这个问题，所以没有这种情况的处理）

如果比较一遍删除的位数不够s，就考虑删除后几位。

在下面代码中，我用置#来表示数字删除，处理的时候再把#一起删除。

完整代码如下：

//贪心算法实现新数最小 /*算法步骤 1.初始化 (函数) 2.比较并删除 3.处理删除不够s位情况 4.输出结果 */ #include<iostream> #include<string> using namespace std; string index="";//记录删除的下标 int count=0;//删除的次数 int main(){string tanxin(string num,int s);//贪心算法函数string process(string minnum);//处理函数int s;//要删除的位数string num="120083";//为了方便定义的时候初始化string minnum;cout<<"请输入您想要去掉几个数字(0~20)：";cin>>s;minnum=tanxin(num,s);cout<<"开始数字为："<<num<<endl;cout<<"处理过后的结果为:";cout<<process(minnum)<<endl;cout<<"删除的下标为:"<<endl;cout<<index<<endl;return 0; } string tanxin(string num,int s){int i,j;string result=num;for(i=0;i<num.size()&&count<s;i++){if(result[i]>result[i+1]){result[i]='#';//置#代表删除index.insert(index.size(),std::to_string(i)); //在尾部插入count++;if((i-1>=0)&&result[i-1]>result[i+1]){result[i-1]='#';index.insert(index.size(),std::to_string(i-1)); //在尾部插入count++;}}}if(count<s){//没有删除三次int s0=3-s;for(i=result.size()-1;i>=s0;i--){result[i]='#';}}return result; } string process(string minnum){//处理找到的字符串string result=minnum,resultsum="";int i,temp=0;//判断前端是否有多余0for(i=0;i<minnum.size();i++){if(result[i]=='0'&&result[i]=='#') {//前面有不为0 且不为#的数字,把标识变量置1temp=1;}if(result[i]=='0'&&temp==0){result[i]='#';}}//去除占位符#for(i=0;i<result.size();i++){if(result[i]!='#') resultsum=resultsum+result[i];//拼接}return resultsum; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071

采用穷举法来实现新数最小，则把所有情况都列举出来，再从中选取最小的情况。在此不做过多讲解，读者可根据需要自行理解。

#include<iostream> #include<string> using namespace std; //采用深度优先遍历的方法，进行穷举 //数据以字符串方式进行存储 /** 输出：去掉的数字位置，以及组成的最小新的正整数 **/ int s;//要挖掉的数字个数 int slen=6;//数字的长度 string minnum="";//最小的数字以字符串的方式进行存储 string index="";//记录删除的下标 int main(){//因为数字过大无法存储，所以用字符串的形式进行比较void dfs(int t,string num);//使用深度优先遍历，挖出字符//返回1 则a大返回0 则b大int compares(string a,string b);//对两个字符串进行比较，看哪个大string process(string minnum);int i;string num="120083";//为了方便先初始化cout<<"请输入您想要去掉几个数字(0~20)：";cin>>s;dfs(0,num);//深度优先遍历，挖哪个好呢？//递归遍历之后返回的是最小的字符串，但是里面含有替换字符，去掉替换字符,并检查输出的字符是否合理cout<<"开始数字为："<<num<<endl;cout<<"处理过后的结果为:";cout<<process(minnum)<<endl;cout<<"删除的下标为:"<<endl;for(i=0;i<index.size();i++){cout<<index[i]<<endl;}return 0; } int compares(string a,string b){//字符串比大小，从高到低一位一位比int i=0,j=0;int lena=a.size();int lenb=b.size();char c='#';//比较时，两个字符串的长度必然相等//if(lena==lenb){while(i<lena&&j<=lenb){if((a[i]==c&&b[i]==c)||(a[i]==c&&b[i]!=c&&b[i]=='0')||(a[i]!=c&&b[i]==c&&a[i]=='0')) {//比较的两个数都被挖空i++;j++;}else if(a[i]==c&&b[i]!=c&&b[i]!='0') return 0;//第一个被挖空，第二个b大else if(a[i]!=c&&b[i]==c&&a[i]!='0') return 1;//第二个被挖空，第一个a大else{if((a[i]-'0')>(b[i]-'0')) return 1;//前一个数a大else if((a[i]-'0')<(b[i]-'0')) return 0;//后一个数b大else{//相等情况i++;j++;}}} //} } //深度优先遍历 void dfs(int t,string num){string sum;int boo;//比较中间变量int i;int index_len=0;//index的长度int count;count=0;for(i=0;i<minnum.size();i++){if(minnum[i]=='#') count++;}//终点if(t>=s){//第一次进入if(minnum==""){minnum=num;return;}else{boo=compares(minnum,num);//1,为minnum大 0，为num大//如果min小则不交换if(boo==0) {return;}//minnum为最小，不用交换else {//如果sum比min小则交换minnum=num;return;}}}else{for(i=0;i<slen;i++){//如果没有上锁if(num[i]!=-1){char c=num[i];//记录所之前的数据num[i]='#';//上锁dfs(t+1,num);num[i]=c;//还原}}} } string process(string minnum){//处理找到的字符串string result=minnum,resultsum="";int i,temp=0;//检测占了哪些下标for(i=0;i<result.size();i++){if(result[i]=='#'){index.insert(index.size(),std::to_string(i)); //在尾部插入}}//判断前端是否有多余0for(i=0;i<minnum.size();i++){if(result[i]=='0'&&result[i]=='#') {//前面有不为0 且不为#的数字,把标识变量置1temp=1;}if(result[i]=='0'&&temp==0){result[i]='#';}}//去除占位符#for(i=0;i<result.size();i++){if(result[i]!='#') resultsum=resultsum+result[i];//拼接}return resultsum; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127