贪心篇+递推
2025-07-25 08:45:34
发布于：北京
10阅读
0回复
0点赞
贪心算法是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致结果全局最优的算法策略。它的核心思想是 “目光短浅”，仅考虑当前步骤的最优解，不考虑后续可能的影响。
贪心算法的基本要素
- 贪心选择性质：问题的整体最优解可以通过一系列局部最优的选择（即贪心选择）来达到。
- 最优子结构性质：问题的最优解包含其子问题的最优解，即当一个问题的最优解包含其子问题的最优解时，称该问题具有最优子结构性质。
贪心算法的执行步骤
1.确定问题的最优子结构：分析问题，确定其是否具有最优子结构，即一个问题的最优解是否包含子问题的最优解。
2.设计贪心策略：针对问题，制定每一步的贪心选择策略，确定在当前状态下如何选择能得到局部最优解。
3.证明贪心策略的正确性：通过数学证明（如归纳法、反证法等），证明所设计的贪心策略能够导致全局最优解。
4.实现算法：根据贪心策略，编写算法代码实现。
举一个样例：
题目描述
今天老师买了 n 盒饼干，给 m 名孩子分发 n 盒饼干，每一个孩子最多只能分发一盒饼干。每一盒饼干的大小各不相同，每个孩子都有一个想要获得的饼干大小。当饼干的大小大于等于孩子想要获得的饼干大小，孩子就会获得满足，现在需要给孩子分发饼干，并且使得尽可能多的孩子获得满足。
代码：
#include <bits/stdc++.h>
using namespace std;
int a[10005],b[10005];
int main() {
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>b[i];
}
sort(a+1,a+1+n);
sort(b+1,b+1+m);
int cnt=0;
int i=1,j=1;
while(i<=n&&j<=m){
if(a[i]>=b[j]){
i++;
j++;
cnt++;
}else{
i++;
}
}
cout<<cnt;
return 0;
}
递推：
冷知识：递推比递归简单
样例题：
这题递推的思路来说的话，只需要推出一个公式（a[i]=a[i-1]+a[i-2]）然后推出数组a，最后输出
AC代码：
#include <bits/stdc++.h>
using namespace std;
long long a[105];
long long n;
long long ddw(long long n){
for(long long i=3;i<=n;i++){
a[i]=a[i-1]+a[i-2];//前缀和公式
}
return a[n];
}
int main() {
a[1]=1;
a[2]=2;
cin>>n;
cout<<ddw(n);
return 0;
}
这里空空如也
有帮助，赞一个