贪心法(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;
}
通过以上代码,我们可以得到最少的区间数量。这个例子展示了贪心法在区间覆盖问题中的应用,通过排序和贪心选择策略,我们选择了最早结束的区间,并保证每次选择的区间是不重叠的。
贪心法是一种常用的算法思想,适用于具有最优子结构和贪心选择性质的问题。通过选择当前状态下的最优选择,期望达到全局最优解。然而,贪心法也有局限性,局部最优不一定是全局最优。因此,在应用贪心法解决问题时,需要仔细分析问题的性质,并考虑贪心选择的正确性。
贪心法在算法设计中有很多应用,例如活动选择问题、钱币找零问题、背包问题、小船过河问题和区间覆盖问题等。这些例子展示了贪心法的思想和具体应用,希望能够帮助你理解和应用贪心法解决问题。
通过不断学习和练习,你将逐渐熟悉贪心法的思想和应用,并能够灵活运用它解决各种实际问题。加油!
️希望本篇文章对你有所帮助。
️如果你有任何问题或疑惑,请随时向提问。
️感谢阅读!
文章浏览阅读1.7k次。第一节 ElasticSearch概述1.1 ES 分布式的全文搜索引擎。它提供了一个分布式多用户能力的全文搜索引擎,基于RESTfulweb接口。ElasticSearch是用Java开发的,并作为Apache许可条款下的开放源码发布,是当前流行的企业级搜索引擎。设计用于云计算中,能够达到实时搜索,稳定,可靠,快速,安装使用方便。构建在全文检索开源软件Lucene之上的Elasticsear..._opensearch wildcard
文章浏览阅读1.3w次,点赞21次,收藏42次。防坑留名:为了避免以后自己遇到什么坑爹的东西,先留脚印给自己。这个hadoop呢,主要是可以让用户可以在不了解分布式底层细节的情况下,开发分布式程序,充分利用集群的威力进行高速运算和存储。这点比较厉害了。它主要是用来做数据分析,支持低端服务器集群(这点美滋滋- - ),先抓取大量数据,利用数据运算分析,获取日志,显示报表~~~~~;_hadoop3.0
文章浏览阅读801次。题目本题是中国海洋大学03-04年第二学期《C程序设计期中考试》第三题编程题的第三题。题目:编写求立方根函数double cube(double x);函数返回参数的立方根。主函数如下:。main() { double cube(double x); double x; scanf("%lf", &x); printf("cube(%lf)=%lf\n", cube(x));}以下是本篇文章正文内容,欢迎朋友们进行指正,一起探讨,共同进步。——来自考研路上的lwj一、解题_double cube(double x);
文章浏览阅读2.9k次,点赞2次,收藏14次。每台都做一做,然后记录在博客里.供自己和大家一起学习._lnhub hackthebox vulnstack vulntarget
文章浏览阅读1.1k次。Debian 6 安装小记07.31.2011 · Posted in LAMP上个月入手了mac,就把thinkpadr400冷落了蛮久。想着太浪费了,于是想着开始折腾系统。最开始是考虑unix中的freebsd, openbsd, netbsd,后来觉得还是回_linux pardus 6.1.0-17-amd64 #1 smp preempt_dynamic debian 6.1.69-1 (2023-12-
文章浏览阅读1.5k次。idea查看UML类图_idea社区版查看类图
文章浏览阅读1.2k次,点赞4次,收藏2次。互联网公司在缓存架构上是区分很大的,往往是根据企业的业务量来进行选择的,可以看如下图在传统的小型互联网公司,采用网页静态化技术,freemarker来加快用户的体验速度,从来来提升响应,但是如果出现了缓存血崩,缓存击穿那么对数据库将会造成很大的压力,可能导致整个架构无法使用一 缓存击穿 缓存穿透是指查询一个一定不存在的数据,由于缓存是不命中时需要从数据库查询,查不到数据则不写..._缓存框架的原理
文章浏览阅读1.1k次,点赞2次,收藏3次。首先了解一下可变参数#include <stdio.h> #define DEBUG(fmt, ...) printf(fmt, __VA_ARGS__)int main(){ DEBUG("you know i am handsome%d,%f,%d", 1000, 1.1, 10); return 0;}输出:you know i am handsome1000,1.100000,10这里的__VA_ARGS__其实就是指代…三个省略号的内容了,这_##__va_args__
文章浏览阅读9.3k次。下面是vue实现,原生html后续贴上来前期准备:引入amap、echarts、echarts-amap依赖,vue的话需要npm安装一下By using script tag<!--引入高德地图JSAPI --> <script src="//webapi.amap.com/maps?v=1.4.15&key=ab99f68b8f9eac7a5287f..._import echartsamap from "echarts-amap";
文章浏览阅读574次。The flowable.form.cfg.xml must contain a bean that has the id ‘formEngineConfiguration’.这个flowable.form.cfg.xml必须包含id为“formEngineConfiguration”的bean。 <bean id="formEngineConfiguration" class="org.flowable.form.engine.impl.cfg.StandaloneFormEngineConfi_form engine is not initialized
文章浏览阅读4.6k次,点赞2次,收藏12次。首先说明,yocto中的依赖本质上是任务之间的依赖,即使是使用DEPENDS或者RDEPENDS定义的两个recipe之间的依赖关系,但实际上在yocto运行时依赖关系还是会体现在这两个recipe中的task之间,即在运行时,yocto会将recipe之间的依赖解析成task之间的依赖。task之间的依赖关系可以分为两种:属于同一个recipe的task之间的依赖或者属于不同recipe的ta..._yocto depends
文章浏览阅读162次。当一个Web系统从日访问量10万逐步增长到1000万,甚至超过1亿的过程中,Web系统承受的压力会越来越大,在这个过程中,我们会遇到很多的问题。为了解决这些性能压力带来问题,我们需要在Web系统架构层面搭建多个层次的缓存机制。在不同的压力阶段,我们会遇到不同的问题,通过搭建不同的服务和架构来解决。Web负载均衡Web负载均衡(Load Balan