【算法篇】贪心算法
目录
贪心算法
贪心算法实际应用
一，零钱找回问题
二，活动选择问题
三，分数背包问题
将数组和减半的最小操作次数
最大数
贪心算法
贪心算法，是一种在每一步选择中都采取当前状态下的最优策略，期望得到全局最优解的算法策略。也就是说，通过局部最优解，期望得到全局最优解。
贪心算法一般按如下步骤执行：
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;
}
};