贪心法(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;
}
通过以上代码,我们可以得到最少的区间数量。这个例子展示了贪心法在区间覆盖问题中的应用,通过排序和贪心选择策略,我们选择了最早结束的区间,并保证每次选择的区间是不重叠的。
贪心法是一种常用的算法思想,适用于具有最优子结构和贪心选择性质的问题。通过选择当前状态下的最优选择,期望达到全局最优解。然而,贪心法也有局限性,局部最优不一定是全局最优。因此,在应用贪心法解决问题时,需要仔细分析问题的性质,并考虑贪心选择的正确性。
贪心法在算法设计中有很多应用,例如活动选择问题、钱币找零问题、背包问题、小船过河问题和区间覆盖问题等。这些例子展示了贪心法的思想和具体应用,希望能够帮助你理解和应用贪心法解决问题。
通过不断学习和练习,你将逐渐熟悉贪心法的思想和应用,并能够灵活运用它解决各种实际问题。加油!
️希望本篇文章对你有所帮助。
️如果你有任何问题或疑惑,请随时向提问。
️感谢阅读!
文章浏览阅读315次。有时候,多么的希望ORACLE能够导出某个视图中的数据,然后通过这个视图来迁移需要的数据,现在ORACLE 12C通过expdp的views_as_tables来实现了该功能,把视图当作一个普通表从而导出数据,导入的时候直接和一个正常表一样,通过视图的导出,表的导入来实现相关需求准备测试环境SQL> SELECT * FROM V$VERSION;BANNER ..._oracle expdp导出数据视图
文章浏览阅读694次。期望DP+思路_51nod1450闯关游戏
文章浏览阅读660次。java计算机毕业设计高校防疫物资管理系统MyBatis+系统+LW文档+源码+调试部署。springboot基于微服务架构的图书借阅系统的设计与实现。ssm基于大数据在线考试系统在线阅卷系统及大数据统计分析。jsp网上花卉销售系统的设计与实现sqlserver。springboot基于VUE的个人记账管理系统。ssm基于SSM的线上家庭医生系统的设计与实现。ssm基于vue的健康餐饮管理系统的设计与实现。ssm疫情背景下基于web的学生信息日报系统。ssm基于用户行为的自动化书籍推荐系统。
文章浏览阅读4k次,点赞4次,收藏15次。问题1:初步解决响应状态418python爬取豆瓣网站电影:url = ‘https://movie.douban.com/?start=0&filter=’import requestsurl = 'https://movie.douban.com/top250?start=0&filter='res =requests.get(url)print(res.status_code)响应状态:418正常返回状态应该是 200问题解决参考链接: req_python r.status_code 403
文章浏览阅读1.1k次,点赞28次,收藏26次。JVM调优
文章浏览阅读729次,点赞26次,收藏17次。本毕业设计旨在利用前端技术HTML、CSS、JavaScript和Vue框架,结合后端技术Node.js和Express框架,以及MySQL 5.7数据库,通过VSCode和Navicat开发工具,实现一个功能完善、操作简便的家用电器电商网站。此外,通过本毕业设计的实践,可以锻炼学生的实际操作能力,提高学生的编程水平,为学生今后的职业生涯打下坚实的基础。HBuilder X是一个专为前端开发者设计的IDE,支持HTML、CSS、JavaScript等前端技术,以及Vue.js框架。_关于家电网站的选题背景和意义
文章浏览阅读214次。1.vue.js简介Vue.js读音 /vjuː/, 类似于 viewVue.js是前端三大新框架:Angular.js、React.js、Vue.js之一,Vue.js目前的使用和关注程度在三大框架中稍微胜出,并且它的热度还在递增。Vue.js可以作为一个js库来使用,也可以用它全套的工具来构建系统界面,这些可以根据项目的需要灵活选择,所以说,Vue.js是一套构建用户界面的渐进式框架。..._把vue当做库使用
文章浏览阅读5.6k次,点赞8次,收藏79次。python+selenium自动填写提交电子表单前两天看到空间里面有人发 问卷星 调查,就想到能不能用 python 和 网页交互 , 自动 填写 电子表单 ,结果还真有,就尝试了一下,有些还没搞清楚,先大概介绍一下,慢慢来吧。首先,安装 selenium ,这个很简单,进入控制台(win+R,输入cmd,回车),输入pip install selenium很快就安装完成了。然..._dd data-value
文章浏览阅读522次。04线程池完整的头文件和实现文件(.c)前提:这里的线程池是基于Linux下C的实现,且在任务的回调函数中只是模拟工作,具体业务需要自己根据实际编写。这里可以举个例子,当客户端请求过来,我们可以将建立好的通信套接字通过任务的void* arg传进来,这样我们就可以在子线程中与客户端进行交互,极大的减少服务器主线程的工作压力。1 头文件#ifndef __THREADPOOL_H_#define __THREADPOOL_H_typedef struct threadpool_t threadpo_线程池 头文件
文章浏览阅读1.9w次,点赞43次,收藏332次。Linux下的web服务器搭建详细过程每次搭建一个服务器之前,比如MySQL、DNS、WEB等首先要挂载磁盘目录文件挂载就是当要使用某个设备时(例如光盘或软盘),必须先将它们对应放到 Linux 系统中的某个目录上。其中对应的目录就叫作挂载点。只有经过操作之后,用户或程序才能访问到这些设备。这个操作过程就叫作文件系统的挂载。这里/dev/sr0是软盘,/mnt/cdrom是挂载点[root@wry139 ~]# mount /dev/sr0 /mnt/cdrom/mount: /dev/sr0 写保_linux搭建web服务器
文章浏览阅读4.8k次,点赞5次,收藏70次。SSM框架配置文件详解在SSM项目当中,所需要的配置文件总共有以下三个:①web.xml ②applicationContext.xml ③springmvc.xml以及两个properties文件jdbc.properties和log4j.properties1.web.xmlweb.xml是ssm项目当中最重要的一个配置文件,当服务启动时会首先加载web.xml这个文件,里面包括了对前端控制器、字符编码的配置案例:<?xml version="1.0" encoding_ssm配置文件
文章浏览阅读6.9k次,点赞3次,收藏27次。这篇文章主要写的是通过手柄控制移动在场景中漫游。 在通过手柄控制移动时,我主要写了两个脚本一个ChildTransform.cs、Move.cs; 1、 ChildTransform这个脚本主要是为了获取头部Y轴方向的转动。以及头部在x、z轴方向的移动。将这个信息赋值给这个脚本绑定的对象身上。 2、 Move这个脚本主要是为了控制玩家的移动的,移动的方向是依据绑定ChildTransf_unity怎么用htc的手柄控制人物移动