贪心法(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;
}
通过以上代码,我们可以得到最少的区间数量。这个例子展示了贪心法在区间覆盖问题中的应用,通过排序和贪心选择策略,我们选择了最早结束的区间,并保证每次选择的区间是不重叠的。
贪心法是一种常用的算法思想,适用于具有最优子结构和贪心选择性质的问题。通过选择当前状态下的最优选择,期望达到全局最优解。然而,贪心法也有局限性,局部最优不一定是全局最优。因此,在应用贪心法解决问题时,需要仔细分析问题的性质,并考虑贪心选择的正确性。
贪心法在算法设计中有很多应用,例如活动选择问题、钱币找零问题、背包问题、小船过河问题和区间覆盖问题等。这些例子展示了贪心法的思想和具体应用,希望能够帮助你理解和应用贪心法解决问题。
通过不断学习和练习,你将逐渐熟悉贪心法的思想和应用,并能够灵活运用它解决各种实际问题。加油!
️希望本篇文章对你有所帮助。
️如果你有任何问题或疑惑,请随时向提问。
️感谢阅读!
文章浏览阅读86次。首发地址:https://yq.aliyun.com/articles/221708谈到机器学习,相信很多除学者都是通过斯坦福大学吴恩达老师的公开课《Machine Learning》开始具体的接触机器学习这个领域,但是学完之后又不知道自己的掌握情况,缺少一些实际的项目操作。对于机器学习的相关竞赛挑战,有些项目的门槛有些高,参加后难以具体的实现,因此造..._scrath五子棋下载
文章浏览阅读83次。原标题:Oracle 12c新特性系列专题-安徽Oracle授权认证中心 随着Oracle database 12c的普及,数据库管理员 (DBA) 的角色也随之发生了转变。 Oracle 12c数据库对 DBA 而言是下一代数据管理。它让 DBA 可以摆脱单调的日常管理任务,能够专注于如何从数据中获取更多价值。未来我们会推出基于Oracle12c的技术文章,帮助DBA尽快掌握新一代数据库的新特性..._ilm add policy row store compress advanced row after
文章浏览阅读150次。问题及代码:*Copyright(c)2016,烟台大学计算机与控制工程学院 *All right reserved. *文件名称:负数把正数赶出队列.cpp *作者:张冰 *完成日期;2016年10月09日 *版本号;v1.0 * *问题描述: 设从键盘输入一整数序列a1,a2,…an,试编程实现: 当ai>0时,ai进队,当ai<0时,将队首元素出队,当ai
文章浏览阅读376次。贪心+构造
文章浏览阅读150次。本文讲的是Linux命名空间学习教程(二) IPC,【编者的话】Docker核心解决的问题是利用LXC来实现类似VM的功能,从而利用更加节省的硬件资源提供给用户更多的计算资源。而 LXC所实现的隔离性主要是来自内核的命名空间, 其中pid、net、ipc、mnt、uts 等命名空间将容器的进程、网络、消息、文件系统和hostname 隔离开。本文是Li..._主机的 ipc 命名空间
文章浏览阅读2w次,点赞5次,收藏7次。在设备上强制安装apk。在app已有的情况下使用-r参数在app版本低于现有版本使用-d参数命令adb install -r -d xxx.apk_adb绕过安装程序强制安装app
文章浏览阅读290次。如果是越界进入硬件错误中断,MSP 或者 PSP 保存错误地址,跳转前会保存上一次执行的地址,lr 寄存器会保存子函数的地址,所以如果在 HardFault_CallBack 中直接调用 C 语言函数接口会间接修改了 lr,为了解决这个问题,直接绕过 lr 的 C 语言代码,用汇编语言提取 lr 寄存器再决定后面的操作。由于 STM32 加入了 FreeRTOS 操作系统,可能导致无法准确定位,仅供参考(日常编程需要考虑程序的健壮性,特别是对数组的访问,非常容易出现越界的情况)。_stm32flash地址越界怎么解决
文章浏览阅读1.8k次。学到了一种操作,说实话,我从来没想过还能这样正常情况下,为了管理方便,许多管理员都会开放MySQL数据库的secure_file_priv,这时就可以导入或者导出数据当我如图输入时,就会在D盘创建一个名为123456.php,内容为<?php phpinfo();?>的文件我们可以利用这一点运用到SQL注入中,从拿下数据库到拿下目标的服务器比如我们在使用联合查询注入,正常是这样的语句http://xxx?id=-1 union select 1,'你想知道的字段的内容或查询语句',
文章浏览阅读2.9w次,点赞12次,收藏63次。感谢原文:https://blog.csdn.net/abc5382334/article/details/24260817感谢原文:https://blog.csdn.net/jiaqingge/article/details/52564348Html CSS的三种链接方式css文本的链接方式有三种:分别是内联定义、链入内部css、和链入外部css1.代码为:<html>..._html链接css代码
文章浏览阅读625次。近几年,蓝牙耳机市场发展迅速,越来越多的消费者希望抛弃线缆,更自由地听音乐,对于运动人士来说,蓝牙耳机的便携性显得尤为重要。但目前市面上的大多数蓝牙耳机实际上都是“有线”的,运动过程中产生的听诊器效应会严重影响听歌的感受。而在“真无线”耳机领域,除了苹果的AirPods外,可供选择的产品并不多,而AirPods又不是为运动场景打造的,防水能力非常差。那么对于喜欢运动又想要“自由”的朋友来说,有没有一款产品能够满足他们的需求呢?下面这十款小编专门为大家搜罗的蓝牙耳机或许就能找到适合的!网红击音F1_适合游戏与运动的高音质蓝牙耳机
文章浏览阅读1k次,点赞6次,收藏7次。在本篇博文中,我们在 iOS 17 beta 4(SwiftUI 5.0)测试版中发现了 SwiftUI 视图首次显示时状态的改变会导致动画“副作用”的问题,并提出多种解决方案。
文章浏览阅读1.9k次。 在 上篇文章–Flutter 实现支持上拉加载和下拉刷新的 ListView 中,我们最终实现的效果是在 listView 上面留下了一段空白,本意是用来加载轮播图的,于是今天就开发了一下,希望能给各位灵感。一 、效果如下说一下大体思路 其实图片展示是用的 PageView ,然后,下面的指示器 是用的 TabPageSelector ,当然整体是用 Stack 包裹起来的。1、..._flutter pageview轮播图 site:csdn.net