/*贪婪法是一个不追求最优解，只希望得到较为满意的解的方法。 因为它省去了为找最优解而穷尽所需的时间，所以贪婪法一般可以快速 得到满意的解。贪婪法在求解过程的每一步都选取一个局部最优的策略， 把问题规模缩小，最后把每一步的结果合并起来形成一个全局解。 */ /*贪婪法的基本步骤： （1）从某个初始解出发 （2）采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到 一部分解，缩小问题规模。 （3）将所有解综合起来 */ //实例 用贪婪法解硬币找零问题 /*假设有一种货币，它的面值为1分，2分，5分和1角的硬币，最少需要多少个硬币来 找出k分钱的零钱。按照贪婪法的思想，需要不断使用面值最大的硬币，如要找零的值 小于最大的硬币值，则尝试第二大的硬币，依次类推。*/ //代码清单： #include<iostream> using namespace std; #define ONEFEN 1 #define TWOFEN 2 #define FIVEFEN 5 #define ONEJIAO 10 int main() { int money; int onefen=0,twofen=0,fivefen=0,onejiao=0; cout<< "输入要找零的钱（以分为单位）:" ; cin>>money; //不断尝试每一种硬币 while(money>=ONEJIAO) { onejiao++; money -=ONEJIAO; } while(money>=FIVEFEN) { fivefen++; money -=FIVEFEN; } while(money>=TWOFEN) { twofen++; money -=TWOFEN; } while(money>=ONEFEN) { onefen++; money -=ONEFEN; } //输出结果 cout<< "1角硬币数："<<onejiao<<endl; cout<< "5分硬币数："<<fivefen<<endl; cout<< "2分硬币数："<<twofen<<endl; cout<< "1分硬币数："<<onefen<<endl; return 0; }