贪心法(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;
}
通过以上代码,我们可以得到最少的区间数量。这个例子展示了贪心法在区间覆盖问题中的应用,通过排序和贪心选择策略,我们选择了最早结束的区间,并保证每次选择的区间是不重叠的。
贪心法是一种常用的算法思想,适用于具有最优子结构和贪心选择性质的问题。通过选择当前状态下的最优选择,期望达到全局最优解。然而,贪心法也有局限性,局部最优不一定是全局最优。因此,在应用贪心法解决问题时,需要仔细分析问题的性质,并考虑贪心选择的正确性。
贪心法在算法设计中有很多应用,例如活动选择问题、钱币找零问题、背包问题、小船过河问题和区间覆盖问题等。这些例子展示了贪心法的思想和具体应用,希望能够帮助你理解和应用贪心法解决问题。
通过不断学习和练习,你将逐渐熟悉贪心法的思想和应用,并能够灵活运用它解决各种实际问题。加油!
️希望本篇文章对你有所帮助。
️如果你有任何问题或疑惑,请随时向提问。
️感谢阅读!
文章浏览阅读122次。还是A+BTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 24568Accepted Submission(s): 11729Problem Description读入两个小于10000的正整数A和B,计算A+B。...
文章浏览阅读419次。HEADERS:在BASIC的基础上,额外记录了请求和响应的头信息。FULL:记录所有请求和响应的明细,包括头信息、请求体、元数据。BASIC:仅记录请求的方法,URL以及响应状态码和执行时间。NONE:不记录任何日志信息,这是默认值。配置Feign日志有两种方式;方式二:java代码实现。注解中声明则代表某服务。方式一:配置文件方式。_feign 日志设置
文章浏览阅读155次。将容器管理的持久性 Bean 用于面向服务的体系结构本文将介绍如何使用 IBM WebSphere Process Server 对容器管理的持久性 (CMP) Bean的连接和持久性逻辑加以控制,使其可以存储在非关系数据库..._javax.ejb.objectnotfoundexception: no such entity!
文章浏览阅读1.5k次。基础java练习题一、递归实现跳台阶从第一级跳到第n级,有多少种跳法一次可跳一级,也可跳两级。还能跳三级import java.math.BigDecimal;import java.util.Scanner;public class Main{ public static void main(String[]args){ Scanner reader=new Scanner(System.in); while(reader.hasNext()){ _java 递归例题
文章浏览阅读1.5k次,点赞6次,收藏6次。目录1.串应用- 计算一个串的最长的真前后缀题目描述输入输出样例输入样例输出题解2.字符串替换(string)题目描述输入输出样例输入样例输出题解3.可重叠子串 (Ver. I)题目描述输入输出样例输入样例输出题解4.字符串操作(string)题目描述输入输出样例输入样例输出题解1.串应用- 计算一个串的最长的真前后缀题目描述给定一个串,如ABCDAB,则ABCDAB的真前缀有:{ A, AB,ABC, ABCD, ABCDA }ABCDAB的真后缀有:{ B, AB,DAB, CDAB, BCDAB_对存储在string数组内的所有以字符‘a’开始并以字符‘e’结尾的单词做加密处理。
文章浏览阅读68次。西安交通大学/算法设计与问题求解/树与二叉树/MOOC_算法设计与问题求解西安交通大学
文章浏览阅读1.6k次。问题:在Vue项目中出现如下错误提示:[Vue warn]: Computed property "totalPrice" was assigned to but it has no setter. (found in <Anonymous>)代码:<input v-model="totalPrice"/>原因:v-model命令,因Vue 的双向数据绑定原理 , 会自动操作 totalPrice, 对其进行set 操作而 totalPrice 作为计..._computed property "totalprice" was assigned to but it has no setter.
文章浏览阅读60次。十分暴力而简洁的解决方式:读取P和T的位置并自动生成唯一正确答案,将题给测点与之对比,不一样就给我爬!_basic 1003 case 1
文章浏览阅读422次。原标题:详解将Web项目War包部署到Tomcat服务器基本步骤详解将Web项目War包部署到Tomcat服务器基本步骤1 War包War包一般是在进行Web开发时,通常是一个网站Project下的所有源码的集合,里面包含前台HTML/CSS/JS的代码,也包含Java的代码。当开发人员在自己的开发机器上调试所有代码并通过后,为了交给测试人员测试和未来进行产品发布,都需要将开发人员的源码打包成Wa..._/opt/bosssoft/war/medical-web.war/web-inf/web.xml of module medical-web.war.
文章浏览阅读3k次,点赞3次,收藏13次。# -*- coding: utf-8 -*-# 简述:这里有四个数字,分别是:1、2、3、4#提问:能组成多少个互不相同且无重复数字的三位数?各是多少?def f(n):list=[]count=0for i in range(1,n+1):for j in range(1, n+1):for k in range(1, n+1):if i!=j and j!=k and i!=k:list.a..._python求从0到9任意组合成三位数数字不能重复并输出
文章浏览阅读1k次,点赞3次,收藏2次。<el-table-column prop="studentSex" label="性别" :formatter="sex"></el-table-column>然后就在vue的methods中写方法就OK了methods: { sex(row,index){ if(row.studentSex == 1){ return '男'; }else{ return '女'; }..._elementui table 性别
文章浏览阅读1.1k次。java文件操作之移动文件到指定的目录_java中怎么将pro.txt移动到design_mode_code根目录下