【算法篇】贪心算法

目录

贪心算法

贪心算法实际应用 

一，零钱找回问题

二，活动选择问题

三，分数背包问题

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

最大数

---

贪心算法

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

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

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;}
};