关于贪心算法的心得体会_学习贪心算法的感悟

导语

本人一向对数字处理一类的算法知识点不够敏感，于是痛定思痛，从leetcode上面刷了一段时间之后，写这篇博客来记录和分享自己的体会。

贪心算法

顾名思义，就是用贪心算法解决题目时，只考虑局部最优解，换言之，要用贪心算法解题，就要保证该问题的整体最优解可化分为一个个局部最优解，（这也是最难的一点）

分析题目是否可用贪心算法

较为简单一类的贪心就是像1.分发饼干，2.硬币找零
等问题，能较为直接的看出每一步。
例）钱币找零问题
假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？
用直觉就能分析出要使纸币最少，就先用大面值来支付。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=7; 
int Count[N]={3,0,2,1,0,3,5};
int Value[N]={1,2,5,10,20,50,100};
  
int solve(int money) 
{
	int num=0;
	for(int i=N-1;i>=0;i--) 
	{
		int c=min(money/Value[i],Count[i]);
		money=money-c*Value[i];
		num+=c;
	}
	if(money>0) num=-1;
	return num;
}
 
int main() 
{
	int money;
	cin>>money;
	int res=solve(money);
	if(res!=-1) cout<<res<<endl;
	else cout<<"NO"<<endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

例2） 跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
1
2
3

分析
这题有两种解法，一种是暴力法，即从a[0]依次用递归开始找到最后，但这样容易超时，不推荐使用。
第二种就是，我们可以用贪心，想到从末尾开始，依次判断从当前点能否到达终点，代码如下

#include<bits/stdc++.h>
using namespace std;
 int a[100];
 int main(){
 	 int n;
 	  cin>>n;
 	  for(int i=0;i<n;i++){
 	  	 cin>>a[i];
	   }
	   for(int i=n-1;i>=0;i--){
	   	if(i+a[i]>=n)
	   	   n=i;//该点能到终点，从该点继续判断 
	   }
	   cout<<n==0 ? 1 :0;
 	return 0;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

以上就是最近的总结体会，欢迎指正