【算法篇】贪心算法

贪心算法

贪心算法实际应用

一，零钱找回问题

二，活动选择问题

三，分数背包问题

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

最大数

贪心算法

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

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

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