【算法篇】贪心算法

贪心算法

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

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

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;
        //处理前导0
        if(ret[0]=='0') return "0";

        return ret;
    }
};