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

faryou

前言
        我是一个正在学习C++算法的小蒟蒻，本文为我的学习记录，记录了贪心算法的基本思路以及一道题目的解决方案。文中题目出自洛谷；本人转载自自己的博客，链接：https://blog.faryou.eu.org/post/95.html；内容十分简单（对于大佬们），不喜轻喷~

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

        你和一群硕鼠做交易，你要买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>n[i+1] && i!=num-1){//第一个条件判断前一个数大于后一个数，第二个防止超界
            del(i);//当左边数>右边数时，删左边数
            i=0;//从头开始判断
        }
        else if(n<=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，再见！

gqy123

瞬间脑洞大开

zyzz1234567890

确实老了，看代码都觉得费劲了。

52PJ070

感谢分享，学习思路，非常棒！

llxgdtop

很久没看算法了，都看不懂了

faryou

llxgdtop 发表于 2024-3-31 16:25
很久没看算法了，都看不懂了

这个应该是属于最简单的算法了

你好，再见

C++会方便很多，string也不用考虑溢出问题，学习了

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

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    int n;
    cin >> s >> n;
    while (n != 0) {
        for (int i = 0; i < s.length(); i++) {
            if (s[i] > s[i + 1]) {
                s.erase(i, 1);
                n--;
                break;
            }
        }
    }
    while (s[0] == '0') s.erase(0, 1);
    if (s.empty()) cout << 0;
    else cout << s;
    return 0;
}

faryou

你好，再见 发表于 2024-3-31 17:09
C++会方便很多，string也不用考虑溢出问题，学习了
[mw_shl_code=cpp,true]#include

我是学算法的，对STL这类语法真是不了解哪个方便用哪个

xiaozui23

for(int i=c;i<=num;i++) n=n[i+1];//将被删数右侧每一位都向左移位 这个是不是应该写成n[i] = n[i+1]?

你好，再见

faryou 发表于 2024-3-31 17:51
我是学算法的，对STL这类语法真是不了解哪个方便用哪个

学习算法那就更应该学习使用c++咯
像遇到排序这些总不能手搓一个吧