论坛网站推广方案,做网站模板的海报尺寸多少,照片生成视频制作软件,成都代做网站目录 贪心算法
贪心算法实际应用
一#xff0c;零钱找回问题
二#xff0c;活动选择问题
三#xff0c;分数背包问题
将数组和减半的最小操作次数
最大数 贪心算法
贪心算法#xff0c;是一种在每一步选择中都采取当前状态下的最优策略#xff0c;期望得到全局最优…目录 贪心算法
贪心算法实际应用
一零钱找回问题
二活动选择问题
三分数背包问题
将数组和减半的最小操作次数
最大数 贪心算法
贪心算法是一种在每一步选择中都采取当前状态下的最优策略期望得到全局最优解的算法策略。也就是说通过局部最优解期望得到全局最优解。 贪心算法一般按如下步骤执行
1问题分解 将原问题转化为一系列子问题。
2贪心选择对每个子问题求解的时候都选择当前看起来“最优的”解法。
3合并解累计局部最优解形成全局解。
4正确性证明通过数学归纳或者替换论证验证。因为贪心策略可能是错误的 先简单理解一下贪心算法
例一找零问题
这个问题在我们日常生活中很普遍。
假设我们现在可以找的零钱面额为【201051】并且每个有无限张。当我们想找k的零钱时怎样可以让钱的张数最少
这里假设k46用 贪心算法的思想每一步尽可能使用面值最大的纸币即可。
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(vectorint w, vectorint v, int cap) { vectorItem 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() { vectorint w { 10,20,30,40,50 }; vectorint 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(vectorint nums) {priority_queuedouble heap;double sum0.0;for(int x:nums){sumx;heap.push(x);}sum/2.0;int count0;while(sum0){double theap.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(vectorint nums) {vectorstring strs;for(auto x:nums)strs.push_back(to_string(x));sort(strs.begin(),strs.end(),[](string s1,string s2){return s1s2s2s1;});string ret;for(auto s:strs)rets;//处理前导0if(ret[0]0) return 0;return ret;}
};
