【算法篇】贪心算法

news/2025/2/12 12:19:06/

目录

贪心算法

贪心算法实际应用 

一,零钱找回问题

二,活动选择问题

三,分数背包问题

将数组和减半的最小操作次数

最大数


贪心算法

贪心算法,是一种在每一步选择中都采取当前状态下的最优策略,期望得到全局最优解的算法策略。也就是说,通过局部最优解,期望得到全局最优解。

贪心算法一般按如下步骤执行:

1,问题分解: 将原问题转化为一系列子问题。

2,贪心选择:对每个子问题求解的时候,都选择当前看起来“最优的”解法。

3,合并解:累计局部最优解形成全局解。

4,正确性证明:通过数学归纳或者替换论证验证。(因为贪心策略可能是错误的)

先简单理解一下贪心算法

例一:找零问题

这个问题在我们日常生活中很普遍。

假设我们现在可以找的零钱面额为【20,10,5,1】,并且每个有无限张。当我们想找k的零钱时,怎样可以让钱的张数最少?

这里假设k=46,用 贪心算法的思想,每一步尽可能使用面值最大的纸币即可。

46->  选一张20  -> 26  -> 选一张20 -> 6-> 选一张5->1->选一张1

例二:最小路径和

给你一个矩阵,求解:从矩阵的左上角出发,只能向下和向右两个方向走,求到达矩阵的右下角过程中,路径上所有元素和的最小值。

贪心算法实际应用 

一,零钱找回问题

假设1元,5元,10元,20元,50元,100元的纸币分别有

c0,c1,c2,c3,c4,c5张 。现在用这些钱来找回k元,求最少使用的张数。

用贪心算法的思想,每一步找钱尽可能使用面值大的。

//单张钱的面额
int signle_money[7] = { 1,2,5,10,20,50,100 };
//对应前的个数
int number_money[7] = {2,5,1,3,4,0,4};

//存放结果
int total[7] = { 0 };

int tanxin(int money)
{
    if (money >= 0)
    {
        //每一步尽量选最大的面额
        for (int i = 6; i >=0; i--)
        {
            total[i] = min(number_money[i], money / signle_money[i]);
            money = money - total[i] * signle_money[i];
        }
        return 0;
    }
    else
    {
        return money;
    }
}
int main()
{
    int k = 0;
    cout << "输入 要找回的零钱" << endl;
    cin >> k;

    if (!tanxin(k))
    {
        cout << "贪心结果为:" << endl;
        for (int i = 0; i < 7; i++)
            cout << signle_money[i] << "元:" << total[i] << "张" << endl;
    }
    else
    {
        cout << "ops wrong number" << endl;
    }
    return 0;
}
 

  

二,活动选择问题

有n个活动,a1,a2,a3...an,这些活动需要在同一天使用同一个教室。每个活动都有一个开始时间si和结束时间fi,一旦被选择后,活动ai就占据半开时间[si,fi)。如果[si,fi)和[sj,fj)互不重叠,那么ai和aj两个活动可以被安排在同一天。该问题是安排这些活动,使尽量多的活动不冲突的举行。

贪心策略:想要使尽量多的活动不冲突,那我们在选择活动时,就尽量选择结束早的活动,为后续留出更多的时间。

//活动安排问题
#include <algorithm>
struct ACT
{
    int start;
    int end;
}activity[100];

//活动的个数
int N;

bool cmp(ACT a, ACT b)
{
    return a.end < b.end;
}

int greedy()
{
    int num = 0;

    for (int i = 0, j = i + 1; i < N; j++)
    {
        if (activity[j].start > activity[i].end)
        {
            i = j;
            num++;
        }
    }

    return num;
}

int main()
{
    cout << "活动的总数:";
    cin >> N;
    cout << "输入每个活动的开始和结束:" << endl;

    for (int i = 0; i < N; i++)
    {
        cin >> activity[i].start;
        cin >> activity[i].end;
    }
    
    //将活动按结束时间排序,升序
    sort(activity, activity + N, cmp);

    //统计结果
    int res = greedy();
    cout << "安排的活动个数:" << res << endl;
    return 0;
}
 

三,分数背包问题

情景描述:给定背包容量和一些物品,每个物品有重量和价值两个属性。允许只取一个物品的一部分加入背包,求问如何才能使背包装的物品价值最大。

与01背包不同,分数背包问题允许将物品的部分装入背包。这意味着我们可以将一个物品分割成任意大小,并根据其重量比例来计算其价值。

贪心策略:

核心思想:按性价比来排序。即每个物品的单位价值:价值/重量。

按照单位价值从高到低对物品进行排序,然后依次考虑每个物品 。

算法步骤:

   1,将所有物品按照单位价值从高到低排序。

    2,遍历排序后的物品。对于每个物品:

  • 如果物品重量小于等于背包剩余容量 ,就将物品装入背包。
  • 如果物品重量大于背包剩余容量,只装入能狗适应当前容量的部分。

//分数背包问题
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Item
{
public:
    int _w;
    int _v;
    Item() = default;
    Item(int w,int v)
        :_w(w)
        ,_v(v)
    {}
};

bool cmp(Item a, Item b)
{
    return a._v / a._w > b._v /a._w;
}

double greed(vector<int>& w, vector<int>& v, int cap)
{
    vector<Item> items(w.size());
    double res = 0;

    for (int i = 0; i < w.size(); i++)
    {
        items[i] = { w[i], v[i] };
    }

    sort(items.begin(), items.end(), cmp);

    for (auto& item : items)
    {
        if (item._w <= cap)
        {
            res += item._v;
            cap -= item._w;
        }
        else
        {
            res += (double)item._v / item._w * cap;
            break;
        }
    }

    return res;
}
int main()
{
    vector<int> w = { 10,20,30,40,50 };
    vector<int> v = { 50,120,150,210,240 };
    //背包容量
    int cap = 50;
    cout << "MAX_value:" << greed(w, v, cap) << endl;

    return 0;
}

                   

将数组和减半的最小操作次数

本题链接:2208. 将数组和减半的最少操作次数 - 力扣(LeetCode)

 贪心策略:每次选出数组中的最大值,对该数减半,直到使数组和减小到一半。

算法步骤:

  • 计算出数组和的一半sum
  • 每次选数组 中最大的数a进行减半,sum-=a/2,找到sum为0结束。

在每次选最大数的时候,我们可以借助优先级队列,快速找的最大值。

class Solution {
public:int halveArray(vector<int>& nums) {priority_queue<double> heap;double sum=0.0;for(int x:nums){sum+=x;heap.push(x);}sum/=2.0;int count=0;while(sum>0){double t=heap.top()/2.0;sum-=t;heap.pop();heap.push(t);count++;}return count;}
};

最大数

本题链接:179. 最大数 - 力扣(LeetCode)

贪心策略:本题可以理解为是对数组nums进行重新“排序”,而传统的排序是根据大小排的,对于本题,则是按照题目要求。

对于nums数组中的两个元素a和b, 我们无法直接确定他们的先后关系,但我们可以从结果角度来看,如果拼接结果ab要比ba好,那么a就应该放在b的前面。

class Solution {
public:string largestNumber(vector<int>& nums) {vector<string> strs;for(auto x:nums)strs.push_back(to_string(x));sort(strs.begin(),strs.end(),[](string s1,string s2){return s1+s2>s2+s1;});string ret;for(auto& s:strs)ret+=s;//处理前导0if(ret[0]=='0') return "0";return ret;}
};


http://www.ppmy.cn/news/1570696.html

相关文章

zzcms接口index.php id参数存在SQL注入漏洞

zzcms接口index.php id参数存在SQL注入漏洞 漏洞描述 ZZCMS 2023中发现了一个严重漏洞。该漏洞影响了文件/index.php中的某些未知功能,操纵参数id会导致SQL注入,攻击可能是远程发起的,该漏洞已被公开披露并可被利用。攻击者可通过sql盲注等手段,获取数据库信息。 威胁等级:…

LLM框架对比选择:MaxKB、Dify、FastGPT、RagFlow【RAG+AI工作流+Agent]

1.MaxKB MaxKB Max Knowledge Base&#xff0c;是一款基于 LLM 大语言模型的开源知识库问答系统&#xff0c;旨在成为企业的最强大脑。它能够帮助企业高效地管理知识&#xff0c;并提供智能问答功能。想象一下&#xff0c;你有一个虚拟助手&#xff0c;可以回答各种关于公司内…

Flink CDC YAML:面向数据集成的 API 设计

摘要&#xff1a;本文整理自阿里云智能集团 、Flink PMC Member & Committer 徐榜江&#xff08;雪尽&#xff09;老师在 Flink Forward Asia 2024 数据集成&#xff08;一&#xff09;专场中的分享。主要分为以下四个方面&#xff1a; Flink CDC YAML API Transform A…

SoC 架构设计全面详解:从基础到实战

一、SoC 是什么&#xff1f;为什么重要&#xff1f; SoC (System on Chip, 片上系统) 是一种将计算核心、存储系统、通信接口以及各种外设集成到一个单一芯片上的高度集成解决方案。它在智能手机、汽车电子、人工智能、工业控制等领域扮演着至关重要的角色。 为什么 SoC 如此重…

Matplotlib基础02-常用图像绘制(折线图/散点图/柱状图/直方图/饼图/箱线图/热图/极坐标图/雷达图/填充图)

常用图像绘制方法 1. 折线图:plt.plot(x,y) 折线图是最常见的图形之一&#xff0c;适用于展示数据随时间或其他变量变化的趋势。 plt.figure(figsize(8,4)) x[Mon, Tue, Wed, Thu, Fri, Sat, Sun] y[53, 65, 32, 54, 68, 76, 102] plt.plot(x, y, markero) plt.ylim(0, 500)…

单片机通讯中的时序图:初学者的入门指南

一、什么是时序图&#xff1f; 在单片机的世界里&#xff0c;时序图是一种非常重要的工具&#xff0c;它用于描述信号在时间上的变化规律。简单来说&#xff0c;时序图就像是信号的“时间线”&#xff0c;它展示了各个信号线在不同时间点上的电平状态。通过时序图&#xff0c;我…

2025.2.9机器学习笔记:PINN文献阅读

2025.2.9周报 文献阅读题目信息摘要Abstract创新点网络架构实验结论缺点以及后续展望 文献阅读 题目信息 题目&#xff1a; GPT-PINN:Generative Pre-Trained Physics-Informed Neural Networks toward non-intrusive Meta-learning of parametric PDEs期刊&#xff1a; Fini…

嵌入式硬件篇---CPUGPUTPU

文章目录 第一部分&#xff1a;处理器CPU&#xff08;中央处理器&#xff09;1.通用性2.核心数3.缓存4.指令集5.功耗和发热 GPU&#xff08;图形处理器&#xff09;1.并行处理2.核心数量3.内存带宽4.专门的应用 TPU&#xff08;张量处理单元&#xff09;1.为深度学习定制2.低精…