js统计网站访问人数,摄影网页设计模板,seo免费入门教程,seo咨询解决方案什么是贪心算法#xff1f;#xff1f;#xff1f;
贪心算法是指通过每一次都选择最优解情况#xff0c;然后通过局部最优从而达到全局最优#xff0c;简单理解为目光短浅#xff0c;走一步看一步。
需要注意的是#xff0c;贪心算法是一种思想#xff0c;而非直接的…什么是贪心算法
贪心算法是指通过每一次都选择最优解情况然后通过局部最优从而达到全局最优简单理解为目光短浅走一步看一步。
需要注意的是贪心算法是一种思想而非直接的方法
下面我们进入具体的贪心算法中来帮助大家理解贪心其思想 一.最少硬币问题
下面我们通过leedcode上面的这题来带大家了解最简单的贪心最少硬币问题
. - 力扣LeetCode 需要注意的是 我们的钱只有三种5 10 20
由于我们开始手里没钱所以如果第一位顾客给的不是5元那么直接false如果是5元
接下来我们就需要统计我们手里的5元钱数和10元钱数注意不需要统计20元钱数因为20元根本不参与找钱然后就是一边统计一边找钱检查是否可行
贪心点如果用户给10元我们只能找5元但是如果用户给20元我们是有选择的可以105也可以3*5所以这里我们优先选择105,就是贪心策略保障手里的5元钱可以尽可能满足更多用户
解题代码
class Solution {
public:bool lemonadeChange(vectorint bills) {if(bills[0]!5){return false;}else{int five0,ten0;for(auto i:bills){if(i5)five;else if(i10){if(five0)return false;else{five--;ten;}}else{if(tenfive){ten--,five--;}else if(five3){five-3;}elsereturn false;}} return true;} }
};
如果你认为选硬币就是贪心问题的话我再带大家看一道题
来源洛谷
硬币问题 - 洛谷 看完题目感觉没错就是通过局部最优从而到全局最优情况好现在我们来看看下面情况
如果n15如果按照贪心思路就是选111111共5个硬币但是如果选5元的只需要3个是不是就错了实际上这题考察的是dp动态规划
如果你学过了dp可以写下但是如果你还没学可以跳过我的代码实现
#includebits/stdc.h
using namespace std;
const int M1e61;
int n;
int dp[M];
int main()
{cinn;for(int i1;in;i){dp[i]dp[i-1]1;//注意{0,1,2,3,4,1,2,3,4,5,2,1};if(i5)dp[i]min(dp[i],dp[i-5]1);if(i11)dp[i]min(dp[i],dp[i-11]1);}coutdp[n]\n; return 0;
} 此时的你是不是非常好奇什么时候是贪心呢
贪心通常有如下两种结构
1.最优子结构性质
当一个问题的最优解包含其子问题的最优解时则此问题具有最优子结构
2.贪心选择性质
问题整体的最优解可以通过一系列局部最优解得到 此时我们回到第二题发现15元钱时选择11元并不是其子问题最优解也无法满足性质2 关于这方面的题我也没有找到太多希望大家谅解
找零_牛客题霸_牛客网
答案
#include bits/stdc.h
using namespace std;
int n,coin;
int main()
{//输入cinn;coin1024-n;int count0;//贪心while(coin){if(coin64){coin-64;count;}else if(coin64coin16){coin-16;count;}else if(coin16coin4){coin-4;count;}else {coin-1;count;}}//输出coutcountendl;return 0;
}
二.活动安排问题
该问题通常又叫区间调度问题
通常是指
有非常的内容例子节目完成这些内需要一定的时间起始时间和结束时间给出问如何合理安排才能尽可能安排最多的内容或者问是否能够全部不冲突
该类问题关键在于选择策略
我们该关注的是哪个时间
A起始时间 B结束时间 C总共用时
很显然我们最应该关注的是B只有这样我们才能保证最大可能容纳更多的内容 如上图我们关注结束时间找最早结束时间然后不断找在上一次结束时间之后的起始时间找最早结束时间直到结束 以上是关于贪心算法思想的前一部分我们之后会出关于后序内容感谢大家的支持
