《算法笔记知识点记录》第四章——算法初步4——贪心

简介: 《算法笔记知识点记录》第四章——算法初步4——贪心

☘前言☘

贪心算是很基础的算法了,在这个文章中我们会接触到一些贪心的算法,希望能跟我一起学习呀。。每篇文章后面都有对应的练习题哦,我自己会写题解给大家作为参考,好了不bb了,我们开始把!




🧑🏻作者简介:一个从工业设计改行学嵌入式的年轻人

✨联系方式:2201891280(QQ)

📔源码地址:https://gitee.com/xingleigao/algorithm-notes

⏳全文大约阅读时间: 120min(有点长,大家忍一下 ,一定会有蜕变的)


简单贪心

贪心法是求解最优化问题的一种方法,考虑的是时时刻刻都是局部最优解,从而最终得到全局最优解的方法。一般来说贪心的证明非常复杂,所以一道题看着像贪心,并且我们无法找到反例推翻贪心的时候就应该大胆的使用它。


PAT B1020月饼

上面的介绍都很模糊,你可能不太能看懂,那我们就直接看一道题,你肯定马上就懂了。


B1020 月饼 (25 分)

题目描述

给定所有种类月饼的库存量、总售价、以及市场的最大需求量,请你计算可以获得的最大收益是多少。销售时允许取出一部分库存。

输入样例

3 20

18 15 10

75 72 45

输出样例

94.50


解题思路

其实很容易想到吧,计算一下每个月饼的单价,每次都选择最贵的进行销售,最终得到的收益一定可以使最终的收益最大。有了思路,代码就很容易了。


#include <cstdio>
#include <algorithm>
using namespace std;
struct yuebing{
    double kucun;
    double shoujia;
    double danjia;
}yue[1009];
bool cmp(yuebing a, yuebing b){
    return a.danjia > b.danjia; //为了贪心排序
}
int main(){
    int n;
    double d; 
    scanf("%d %lf", &n, &d);
    for(int i = 0;i < n;++i)    scanf("%lf",&yue[i].kucun);
    for(int i = 0;i < n;++i){
        scanf("%lf",&yue[i].shoujia);
        yue[i].danjia = yue[i].shoujia / yue[i].kucun;//直接计算
    }
    sort(yue, yue + n, cmp);
    double ans = 0;
    for(int i = 0;i < n;++i)
        if(d > yue[i].kucun)    ans += yue[i].shoujia, d -= yue[i].kucun;
        else {  //不够了 只卖需要的库存
            ans += yue[i].danjia * d;
            break;
        }
    printf("%.2lf\n",ans);
    return 0;
}


需要注意的坑:


库存和总售价都是正数。所以可能是小数,所以用double。

虽然总需求量是正整数,但是总监计算的时候会减,可能会出问题,所以直接用double省心。

B 1023 组个最小数 (20 分)

B 1023 组个最小数 (20 分))

题目描述

给定数字 0-9 各若干个。你可以以任意顺序排列这些数字,但必须全部使用。目标是使得最后得到的数尽可能小(注意 0 不能做首位)。例如:给定两个 0,两个 1,三个 5,一个 8,我们得到的最小的数就是 10015558。

现给定数字,请编写程序输出能够组成的最小的数。

输入样例

2 2 0 0 0 3 0 0 1 0

输出样例

10015558


解题思路

其实很简单,就是第一位选择非0的最小值,后面依次打印出最小值就好了。


#include <cstdio>
int main(){
    int hash[10] = {0};
    int tmp;
    for(int i = 0;i < 10;++i)   scanf("%d",&tmp),hash[i] = tmp;
    for(int i = 1;i < 10;++i)       //第一位
        if(hash[i]){
            printf("%d",i);
            --hash[i];
            break;
        }
    for(int i = 0;i < 10;++i)   
        while(hash[i]){
            printf("%d",i);
            --hash[i];
        }
    puts("");//最后的回车
    return 0;
}

区间贪心

给一个例子:435. 无重叠区间


问题的问题是怎么取出最少的区间使最终的区间不重叠。那么其实它的类似问题是怎么选出尽可能多的不重叠区间,这就是区间贪心的应用之处。


a4208293c87e4ab882d85a7cf0016b2a.png

对于第一种情况,显然我们需要选择包含长度小的 也就是I1


对于第二种情况,我们将左端点从大到小排列我们可以发现

如果去掉右边的一部分 左边的部分总是被I2包含,同理可以得到I3

和I1也是一样的道理,我们选择I1 最好。也就是每次我们都选择左端点最大的区间。

所以我们就是将左端点从大到小排列,如果相同则按照右端点从小到大(对应第一种情况),然后每次选择左端点最大的区间,如果下一个区间与选中区间不重叠就新增一个区间就好了。

代码如下:


struct node{
    int x;
    int y;
}Node[100009];
int cmp(struct node *a,struct node *b){
        if(a->x != b->x)    return a->x > b->x ? -1 : 1;
    else return a->y < b->y ? -1 : 1;
}
int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize){
    for(int i = 0;i < intervalsSize;++i) Node[i].x = intervals[i][0],Node[i].y = intervals[i][1];
    qsort(Node,intervalsSize,sizeof(struct node),cmp);
    int ans = 1, last = Node[0].x;
    for(int i = 1;i < intervalsSize;++i)
        if(Node[i].y <= last){
            last = Node[i].x;
            ans++;
        }
    return intervalsSize - ans;
}

fa4e04b8d4ad4b9d8e1d500e3280d024.png



时间复杂度还行,因为利用了新的节点,所以空间比不过。文章里用力扣是为了表现思想,大家平时刷题还是多用OJ,在力扣的代码很不规范,习惯不好,大家加油!


推荐专栏

🍭《算法笔记》记录🍭

👻算法笔记刷题👻


🐳课后习题

我写完会放题解,大家写完了可以在评论区打卡哟!题解我放评论区吧,这样不用修改文章。


88d01f4c5da2aea830047063df81da3.png

题解:评论区见,置顶没有就是我没写完0.0,大佬们刷完打个卡

大家加油冲!!!!


相关文章
|
1月前
|
算法 索引
❤️算法笔记❤️-(每日一刷-141、环形链表)
❤️算法笔记❤️-(每日一刷-141、环形链表)
46 0
|
1月前
|
算法 API 计算机视觉
人脸识别笔记(一):通过yuface调包(参数量54K更快更小更准的算法) 来实现人脸识别
本文介绍了YuNet系列人脸检测算法的优化和使用,包括YuNet-s和YuNet-n,以及通过yuface库和onnx在不同场景下实现人脸检测的方法。
35 1
|
1月前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
59 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-160、相交链表)
❤️算法笔记❤️-(每日一刷-160、相交链表)
17 1
|
1月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
101 0
|
1月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
14 0
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
31 0
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-26、删除有序数组的重复项)
❤️算法笔记❤️-(每日一刷-26、删除有序数组的重复项)
23 0
|
27天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
11天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。