推荐返现金,月入2000多
定义
贪心算法，又名贪婪法，是寻找最优解问题的常用方法（其实得到的往往是近似最优解），这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。
基本步骤
- 步骤 1：从某个初始解出发；
- 步骤 2：采用迭代的过程，当可以向目标前进一步时，就根据
局部最优策略，得到一部分解，缩小问题规模； - 步骤 3：将所有解综合起来。
实例：找零钱问题
假设你开了间小店，不能电子支付，钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币，如果你是售货员且要找给客户 41 分钱的硬币，如何安排才能找给客人的钱既正确且硬币的个数又最少？
分析步骤
问题的解的限制条件为个数最少，符合寻找最优解问题的特征
分解问题：取一个硬币，使用贪心策略，为了使总硬币个数最少，硬币取尽可能最大面额的，然后计算剩余找零额
对上述子问题迭代，得到最优解
代码实现
#include<iostream>
using namespace std;
#define ONEFEN 1
#define FIVEFEN 5
#define TENFEN 10
#define TWENTYFINEFEN 25
int main()
{
int sum_money=41;
int num_25=0,num_10=0,num_5=0,num_1=0;
//不断尝试每一种硬币
while(sum_money>=TWENTYFINEFEN) { num_25++; sum_money -=TWENTYFINEFEN; }
while(sum_money>=TENFEN) { num_10++; sum_money -=TENFEN; }
while(sum_money>=FIVEFEN) { num_5++; sum_money -=FIVEFEN; }
while(sum_money>=ONEFEN) { num_1++; sum_money -=ONEFEN; }
//输出结果
cout<< "25分硬币数："<<num_25<<endl;
cout<< "10分硬币数："<<num_10<<endl;
cout<< "5分硬币数："<<num_5<<endl;
cout<< "1分硬币数："<<num_1<<endl;
return 0;
}
扩展：最优解
将问题中的硬币种类改为 25 分、20 分、10 分、5 分和 1 分五种硬币，找零额依然为 41 分
此时使用贪心算法得到结果与原问题相同：25 分 1 枚，10 分 1 枚，5 分 1 枚，1 分 1 枚，共 4 枚
但该解并非最优解，最优解为：20 分 2 枚，1 分 1 枚，共 3 枚
可以看出贪心算法的局限性是不能得到确定的全局最优解，但优点就是速度快且占用资源少