【算法教程】贪心算法讲解及详细案例说明

faryou

前言
        说句真心话，我以前写的文章中很大一部分都有些水，现在开始，我的算法教程系列正式启动。此系列内容更新十分缓慢，请务必耐心等待~

贪心算法
        顾名思义，贪心算法是指在每个局部都采用最优解的方法，当然，这种解法对于整体来说并不一定最优解。例如下面这个问题就是典型的贪心算法解题：

        你和一群硕鼠做交易，你要买12斤苹果，而以下三只硕鼠有三个价格，请你选择最优的方案：
                第一只硕鼠：共有20斤苹果，其中4斤7元；
                第二只硕鼠：共有10斤苹果，其中2斤3元；
                第三只硕鼠：共有15斤苹果，其中5斤8元。

        以上是一个很简单的贪心问题“硕鼠的交易”。很显然，我们要选择单价最为便宜的第二只硕鼠的单价进行交易，但因为第二只硕鼠总共只有10斤苹果，因此我们在买完了第二只硕鼠的苹果之后还需要再买价格第二便宜的第三只硕鼠的2斤苹果。

案例
        这题名叫删数问题。讲一下思路：因为要删到最小数，所以可以从左到右依次判断，如果左侧数大于右侧数，则删左侧数。之后继续判断。如果最后一个数最大，则删这个数。这种做法的思路就是使高位数小，整个数便也小了。这是贪心的思想。下面是代码实现：

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>//定义头文件
using namespace std;//标准库
//说明：本人比较喜欢C风格的程序，因此没怎么涉及到C++的特性（如cout、cin、string等）
//by:faryou
char n[255];//因为位数很多，长整型显然无法存下250位，故使用字符串
int k,num=0,i=0;//k对应题目中的k，num为记录变量（记录剩余的位数，可以理解为右指针），i为指针（记录判断到的位数）
void del(int c){//删数函数，原理是将被删数右侧每一位都往左移动一位
 for(int i=c;i<=num;i++) n[i]=n[i+1];//将被删数右侧每一位都向左移位
 k--;//要删的数减少一个
 num--;//右指针减1
}
int main(){
scanf("%s%d",&n,&k);//读入数据
while(n[num]!='\0') num++;//取总位数
while(1){//死循环，之后有跳出条件
if(k<=0) break;//当要删的数还剩0个时，结束循环
if(n[i]>n[i+1] && i!=num-1){//第一个条件判断前一个数大于后一个数，第二个防止超界
del(i);//当左边数>右边数时，删左边数
i=0;//从头开始判断
}
else if(n[i]<=n[i+1] && i!=num-1) i++;//当前面条件不成立时，判断下一个数
else if(i==num-1){//当判断到最后一个数时
del(num-1);//删最后一个数
i=0;//从头开始判断
}
}
while(n[0]=='0') del(0);//将前缀零删去
if(n[0]=='\0') n[0]='0';//特判，如果前面0被删光了，添一个0
printf("%s",n);//以字符串形式输出
return 0;//结束程序
}

        说明：个人喜欢使用C风格，因此此处使用了char数组存储数据，而且这里char比string方便（char数组末尾有'\0'做结束标识符，不需要再开一个变量存剩余位数，再拿for循环输出）。

总结
        贪心算法本身不难，就是在某些解题思路上要大胆一些。在编写C++程序时，使用C风格也是一个不错的选择。我是faryou，再见！