锐客网

  1. 首页 > it技术 > >

蓝桥杯准备每日练习|【蓝桥杯方法篇】贪心算法详解一

算法贪心算法蓝桥杯


文章目录

  • 一，贪心算法
  • 二，以分配题为例
    • 2.1,饼干分配
    • 2.2,最少硬币问题
  • 三，区间问题

欢迎关注
蓝桥杯每日练习合集
共同努力。
一，贪心算法 【蓝桥杯准备每日练习|【蓝桥杯方法篇】贪心算法详解一】贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心——>局部最优——>全局最优
缺点：
有写情况并不适用。
缺点：
不从总体上考虑其它可能情况，每次选取局部最优解，不再进行回溯处理，所以很少情况下得到最优解。得到的解不代表是最优解。
二，以分配题为例 2.1,饼干分配 题目描述
有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃 最多一个饼干，且只有饼干的大小大于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩 子可以吃饱。
输入输出样例
输入两个数组，分别代表孩子的饥饿度和饼干的大小。输出最多有多少孩子可以吃饱的数 量。
Input: 1,2 1,2,3 Output: 2

思路分析：这道题可以使用贪心算法，我们可以将孩子饥饿度大小排序，再吧饼干大小排序，尽量把小饼干分出去。
看我的解题代码：
#include using namespace std; //上进小菜猪 int main() { int a=0,b[100],c=0; while(cin>>a) { b[c++]=a; if(cin.get()=='\n')break; } int a1=0,b1[100],c1=0; while(cin>>a1) { b[c1++]=a1; if(cin.get()=='\n')break; } sort(b,b+c); sort(b1,b1+c1); int cout1=0; for(int i=0,j=0; i

2.2,最少硬币问题 题目;
有1、2、5、10、20、50、100七种面值的硬币，要支付指定的金额，问怎么支付所用的硬币个数最少
输入：
157

输出：
4

思路：
可以使用贪心算法，以大数优先，这样就可以保持支付使用的硬币最少。
看我的解题代码；
#include using namespace std; int main() { int x; cin>>x; int a[10]={1,2,5,10,20,50,100}; int cout1=0; while(x) { for(int i=6; i>=0; i--) { if(x>=a[i]) { cout1++; x-=a[i]; break; } } } cout<

三，区间问题 区间问题较为复杂，情况多变，今天时间有点晚，明天还需要仔细学习，后需更新【蓝桥杯方法篇】贪心算法详解二，主要攻克贪心算法的区间问题的相关思路。
区间问题详细细分：
1.区间选取
2.区间选点问题
3.区间完全覆盖问题
4.区间分组问题
5.给定区间，求覆盖的最大长度问题

    推荐阅读


    上一篇：【区块链技术】区块链入门详解①

    下一篇：Python|Python爬虫-获得某一链接下的所有超链接