贪心法(Greedy Algorithm)是一种常见的算法思想,它在每一步选择中都采取当前状态下最优的选择,以期望获得全局最优解。贪心法通常适用于问题具有最优子结构和贪心选择性质的情况。
贪心法适用于满足以下两个条件的问题:
贪心法的使用步骤如下:
贪心法的主要缺点是局部最优不一定是全局最优。由于贪心法每一步只考虑当前状态下的最优选择,并没有考虑到全局的情况,因此在某些情况下可能得不到最优解。在应用贪心法解决问题时,需要仔细分析问题的性质,判断贪心法是否适用。
贪心法在实际问题中有很多应用,下面介绍几个经典的例子:
活动选择问题是一个经典的贪心法应用。给定一组活动,每个活动都有一个开始时间和结束时间,要求选择出最多的互不冲突的活动。
思路解析:
count
,表示选择的活动数量。count
即为选择的活动数量。表格解析:
活动编号 | 开始时间 | 结束时间 |
---|---|---|
1 | 1 | 4 |
2 | 3 | 5 |
3 | 0 | 6 |
4 | 5 | 7 |
5 | 3 | 9 |
6 | 5 | 9 |
7 | 6 | 10 |
8 | 8 | 11 |
9 | 8 | 12 |
10 | 2 | 14 |
11 | 12 | 16 |
流程图解析:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Activity {
int start;
int end;
};
bool compare(Activity a, Activity b) {
return a.end < b.end;
}
int maxActivities(vector<Activity>& activities) {
sort(activities.begin(), activities.end(), compare);
int count = 1;
int end = activities[0].end;
for (int i = 1; i < activities.size(); i++) {
if (activities[i].start >= end) {
count++;
end = activities[i].end;
}
}
return count;
}
int main() {
vector<Activity> activities = {
{
1, 4}, {
3, 5}, {
0, 6}, {
5, 7}, {
3, 9}, {
5, 9}, {
6, 10}, {
8, 11}, {
8, 12}, {
2, 14}, {
12, 16}};
int maxCount = maxActivities(activities);
cout << "最多的互不冲突的活动数量为:" << maxCount << endl;
return 0;
}
通过以上代码,我们可以得到最多的互不冲突的活动数量。这个例子展示了贪心法在活动选择问题中的应用,通过排序和贪心选择策略,我们选择了最多的互不冲突的活动。
钱币找零问题是另一个常见的贪心法应用。给定一定面值的钞票和一个需要找零的金额,要求找出最少的钞票数量。
思路解析:
count
,表示所需钞票的数量。count
即为所需钞票的数量。表格解析:
面值 | 数量 |
---|---|
50 | 2 |
20 | 0 |
10 | 1 |
5 | 0 |
1 | 2 |
流程图解析:
graph LR
A[初始化] --> B[选择第一个面值的钞票]
B --> C[待找零金额是否为0]
C --> |是| F[结束]
C --> |否| D[当前面值是否小于等于待找零金额]
D --> |是| E[加入找零结果,并更新待找零金额]
D --> |否| G[选择下一个面值的钞票]
E --> G
G --> C
#include <iostream>
#include <vector>
using namespace std;
int minCoins(vector<int>& coins, int amount) {
int count = 0;
for (int i = 0; i < coins.size(); i++) {
while (amount >= coins[i]) {
amount -= coins[i];
count++;
}
}
return count;
}
int main() {
vector<int> coins = {
1, 5, 10, 25};
int amount = 67;
int minCount = minCoins(coins, amount);
cout << "最少的钞票数量为:" << minCount << endl;
return 0;
}
通过以上代码,我们可以得到最少的钞票数量。这个例子展示了贪心法在钱币找零问题中的应用,通过贪心选择策略,我们选择了面值最大的钞票来找零,从而达到最少的钞票数量。
背包问题是一个经典的动态规划问题,也可以使用贪心法进行求解。给定一组物品,每个物品都有一个重量和价值,背包有一定的容量限制,要求选择一些物品放入背包中,使得总价值最大。
思路解析:
maxValue
,表示背包中物品的总价值。capacity
,表示背包的剩余容量。maxValue
为当前价值,capacity
为剩余容量减去当前物品的重量。maxValue
上,然后结束遍历。maxValue
即为背包中物品的总价值。表格解析:
物品编号 | 重量 | 价值 | 单位价值 |
---|---|---|---|
1 | 10 | 60 | 6 |
2 | 20 | 100 | 5 |
3 | 30 | 120 | 4 |
流程图解析:
graph LR
A[初始化] --> B[选择第一个物品]
B --> C{背包剩余容量是否为0}
C --> |是| F[结束]
C --> |否| D{当前物品重量是否小于等于背包剩余容量}
D --> |是| E[将物品放入背包,并更新maxValue和capacity]
D --> |否| G[计算当前物品的单位价值乘以背包剩余容量,并加到maxValue上,然后结束遍历]
E --> G
G --> C
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Item {
int weight;
int value;
};
bool compare(Item a, Item b) {
double ratioA = (double)a.value / a.weight;
double ratioB = (double)b.value / b.weight;
return ratioA > ratioB;
}
double maxValue(vector<Item>& items, int capacity) {
sort(items.begin(), items.end(), compare);
double maxValue = 0.0;
for (int i = 0; i < items.size(); i++) {
if (capacity >= items[i].weight) {
maxValue += items[i].value;
capacity -= items[i].weight;
} else {
maxValue += capacity * ((double)items[i].value / items[i].weight);
break;
}
}
return maxValue;
}
int main() {
vector<Item> items = {
{
10, 60}, {
20, 100}, {
30, 120}};
int capacity = 50;
double maxVal = maxValue(items, capacity);
cout << "背包中物品的最大总价值为:" << maxVal << endl;
return 0;
}
通过以上代码,我们可以得到背包中物品的最大总价值。这个例子展示了贪心法在背包问题中的应用,通过排序和贪心选择策略,我们选择了单位价值最高的物品放入背包,从而达到最大的总价值。
小船过河问题是一个经典的贪心法应用。假设有一条河,河中有一些石头,每块石头的位置和大小都不同,要求找到一种过河方案,使得每次跳石头的距离尽可能小。
思路解析:
maxDistance
,表示每次跳石头的最大距离。maxDistance
为最大距离。maxDistance
即为每次跳石头的最大距离。
表格解析:
石头编号 | 位置 |
---|---|
1 | 0 |
2 | 2 |
3 | 4 |
4 | 7 |
5 | 8 |
6 | 9 |
流程图解析:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxDistance(vector<int>& stones) {
sort(stones.begin(), stones.end());
int maxDistance = 0;
for (int i = 1; i < stones.size(); i++) {
maxDistance = max(maxDistance, stones[i] - stones[i - 1]);
}
return maxDistance;
}
int main() {
vector<int> stones = {
2, 5, 7, 10, 12};
int maxDist = maxDistance(stones);
cout << "每次跳石头的最大距离为:" << maxDist << endl;
return 0;
}
通过以上代码,我们可以得到每次跳石头的最大距离。这个例子展示了贪心法在小船过河问题中的应用,通过排序和贪心选择策略,我们选择了相邻石头之间的最大距离作为每次跳石头的最大距离。
区间覆盖问题是一个经典的贪心法应用。给定一组区间,要求选择最少的区间,使得它们的并集覆盖了整个区间。
思路解析:
count
,表示最少的区间数量。end
,表示当前的最远结束时间。end
,则选择该区间,并更新end
为当前区间的结束时间。count
即为最少的区间数量。表格解析:
区间编号 | 开始时间 | 结束时间 |
---|---|---|
1 | 1 | 4 |
2 | 3 | 5 |
3 | 0 | 6 |
4 | 5 | 7 |
5 | 3 | 9 |
6 | 5 | 9 |
7 | 6 | 10 |
8 | 8 | 11 |
9 | 8 | 12 |
10 | 2 | 14 |
11 | 12 | 16 |
流程图解析:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Interval {
int start;
int end;
};
bool compare(Interval a, Interval b) {
return a.end < b.end;
}
int minIntervals(vector<Interval>& intervals) {
sort(intervals.begin(), intervals.end(), compare);
int count = 1;
int end = intervals[0].end;
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i].start > end) {
count++;
end = intervals[i].end;
}
}
return count;
}
int main() {
vector<Interval> intervals = {
{
1, 4}, {
3, 5}, {
0, 6}, {
5, 7}, {
3, 9}, {
5, 9}, {
6, 10}, {
8, 11}, {
8, 12}, {
2, 14}, {
12, 16}};
int minCount = minIntervals(intervals);
cout << "最少的区间数量为:" << minCount << endl;
return 0;
}
通过以上代码,我们可以得到最少的区间数量。这个例子展示了贪心法在区间覆盖问题中的应用,通过排序和贪心选择策略,我们选择了最早结束的区间,并保证每次选择的区间是不重叠的。
贪心法是一种常用的算法思想,适用于具有最优子结构和贪心选择性质的问题。通过选择当前状态下的最优选择,期望达到全局最优解。然而,贪心法也有局限性,局部最优不一定是全局最优。因此,在应用贪心法解决问题时,需要仔细分析问题的性质,并考虑贪心选择的正确性。
贪心法在算法设计中有很多应用,例如活动选择问题、钱币找零问题、背包问题、小船过河问题和区间覆盖问题等。这些例子展示了贪心法的思想和具体应用,希望能够帮助你理解和应用贪心法解决问题。
通过不断学习和练习,你将逐渐熟悉贪心法的思想和应用,并能够灵活运用它解决各种实际问题。加油!
️希望本篇文章对你有所帮助。
️如果你有任何问题或疑惑,请随时向提问。
️感谢阅读!
文章浏览阅读6.2k次,点赞6次,收藏26次。我是一个深度学习代码小白,请你用中文写上注释,能让我能轻松理解下面这段代码。注意包含所有函数、调用和参数的注释。以同样的python代码块样式返回你写的代码给我。代码看累了,就看《动手学深度学习》文档:基于PyTorch框架,从底层函数实现基础功能,再到框架的高级功能。努力上路的小白一枚,麻烦路过的大佬指导一二,同时希望能和大家交流学习~争取更新学习这个文档的专栏,记录学习过程。量身定做了一套话术hhh,亲身测试还不错。这个感觉更浅一点儿,之后复习看吧。20天吃掉那只Pytorch。_深度学习程序怎么读
文章浏览阅读2.7w次,点赞126次,收藏1.2k次。耗废1024根秀发,Java学习路线图来了,整合了自己所学的所有技术整理出来的2022最新版Java学习路线图,适合于初、中级别的Java程序员。_java学习路线
文章浏览阅读4.4k次。1.7-savingPNG介绍代码详情函数详解savePNGFile()源码savePNGFile()源码提示savePNGFile()推荐用法处理结果代码链接介绍PCL提供了将点云的值保存到PNG图像文件的可能性。这只能用有有序的云来完成,因为结果图像的行和列将与云中的行和列完全对应。例如,如果您从类似Kinect或Xtion的传感器中获取了点云,则可以使用它来检索与该云匹配的640x480 RGB图像。代码详情#include <pcl / io / pcd_io.h>#incl_pcl::io:savepng
文章浏览阅读936次。吸引妹子的关键点不在于喝什么咖啡,主要在于竖立哪种男性人设。能把人设在几分钟内快速固定下来,也就不愁吸引对口的妹子了。我有几个备选方案,仅供参考。1. 运动型男生左手单手俯卧撑,右手在键盘上敲代码。你雄壮的腰腹肌肉群活灵活现,简直就是移动的春药。2.幽默男生花 20 块找一个托(最好是老同学 or 同事)坐你对面。每当你侃侃而谈,他便满面涨红、放声大笑、不能自已。他笑的越弱_咖啡厅写代码
文章浏览阅读1.2w次,点赞5次,收藏5次。今天 (应该是昨天了,昨晚太晚了没发出去)下午参加了腾讯WXG的面委会面试。前面在牛客上搜索了面委会相关的面经普遍反映面委会较难,因为都是微信的核心大佬,问的问题也会比较深。昨晚还蛮紧张的,晚上都没睡好。面试使用的是腾讯会议,时间到了面试官准时进入会议。照例是简单的自我介绍,然后是几个常见的基础问题:例如数据库索引,什么时候索引会失效、设计模式等。这部分比较普通,问的也不是很多,不再赘述。现在回想下,大部分还是简历上写的技能点。接下来面试官让打开项目的代码,对着代码讲解思路。我笔记本上没有这部分代码,所_腾讯面委会面试是什么
文章浏览阅读382次,点赞3次,收藏4次。AI绘画自动生成器是一种利用人工智能技术,特别是深度学习算法,来自动创建视觉艺术作品的软件工具。这些工具通常基于神经网络模型,如生成对抗网络(GANs),通过学习大量的图像数据来生成新的图像。AI绘画自动生成器作为艺术与科技结合的产物,正在开启艺术创作的新篇章。它们不仅为艺术家和设计师提供了新的工具,也为普通用户提供了探索艺术的机会。随着技术的不断进步,我们可以预见,AI绘画自动生成器将在未来的创意产业中发挥越来越重要的作用。
文章浏览阅读1.7k次。理解为ListView 的三种形式吧ListView 默认构造但是这种方式创建的列表存在一个问题:对于那些长列表或者需要较昂贵渲染开销的子组件,即使还没有出现在屏幕中但仍然会被ListView所创建,这将是一项较大的开销,使用不当可能引起性能问题甚至卡顿直接返回的是每一行的Widget,相当于ios的row。行高按Widget(cell)高设置ListView.build 就和io..._flutter listview.separated和listview.builder
文章浏览阅读1.4k次,点赞4次,收藏14次。废话不多说直接上干货1.js运行机制JavaScript单线程,任务需要排队执行同步任务进入主线程排队,异步任务进入事件队列排队等待被推入主线程执行定时器的延迟时间为0并不是立刻执行,只是代表相比于其他定时器更早的被执行以宏任务和微任务进一步理解js执行机制整段代码作为宏任务开始执行,执行过程中宏任务和微任务进入相应的队列中整段代码执行结束,看微任务队列中是否有任务等待执行,如果有则执行所有的微任务,直到微任务队列中的任务执行完毕,如果没有则继续执行新的宏任务执行新的宏任务,凡是在..._前端面试
文章浏览阅读1k次。(3)若没有查到,则将请求发给根域DNS服务器,并依序从根域查找顶级域,由顶级查找二级域,二级域查找三级,直至找到要解析的地址或名字,即向客户机所在网络的DNS服务器发出应答信息,DNS服务器收到应答后现在缓存中存储,然后,将解析结果发给客户机。(3)若没有查到,则将请求发给根域DNS服务器,并依序从根域查找顶级域,由顶级查找二级域,二级域查找三级,直至找到要解析的地址或名字,即向客户机所在网络的DNS服务器发出应答信息,DNS服务器收到应答后现在缓存中存储,然后,将解析结果发给客户机。_linux
文章浏览阅读7.9k次,点赞26次,收藏66次。HTML DOM——文档元素的操作1、通过id获取文档元素任务描述相关知识什么是DOM文档元素节点树通过id获取文档元素代码文件2、通过类名获取文档元素任务描述相关知识通过类名获取文档元素代码文件3、通过标签名获取文档元素任务描述相关知识通过标签名获取文档元素获取标签内部的子元素代码文件4、html5中获取元素的方法一任务描述相关知识css选择器querySelector的用法代码文件5、html5中获取元素的方法二任务描述相关知识querySelectorAll的用法代码文件6、节点树上的操作任务描述相关_javascript学习手册十三:html dom——文档元素的操作(一)
文章浏览阅读132次。《LeetCode学习》172. 阶乘后的零(java篇)_java 给定一个整数n,返回n!结果尾数中零的数量
文章浏览阅读426次。请注意,本文将要给大家分享的并不是开启公众号的安全操作风险提醒,而是当公众号粉丝给公众号发消息的时候,公众号的管理员和运营者如何能在手机上立即收到消息通知,以及在手机上回复粉丝消息。第一步:授权1、在微信中点击右上角+,然后选择“添加朋友”,然后选择“公众号”,然后输入“微小助”并关注该公众号。2、进入微小助公众号,然后点击底部菜单【新增授权】,如下图所示:3、然后会打开一个温馨提示页面。请一定要..._php微信公众号服务提示