1.简介
贪心算法是一种求局部最优解的方法,及将一个问题拆分为多个小步骤,对每一个小步骤进行考虑,不从大局出发,对于每一步去思考他的最优方案。这种思路经常用于求解最短路径问题,对每一个节点进行分组化考虑。本文将会采用一个简短的例子 ,来让读者能入门。并在原有基础上进行提升。在不久笔者还会对该算法进行拔高,链接将会作为引文放在这里。
2.问题叙述
在天河世界,小远去商店想买一个本子,但碰到了爱刁难人的售货员。小远选中了一个本子,售价69元。他想去结账时候,售货员说‘我不接受太多硬币,你必须用最少的硬币数量来支付这69元,如果你可以做到,我就给你打对折”。这时候小远犯难了。小远手里只有10元,5元,2元的硬币,聪明的小朋友,你能告诉小远他该如何去付钱吗?(小远手里的钱足够多)
2.1问题分析
小远手里有足够的钱,最大金额是10元。从贪心算法的角度去看,金额越大所需要的零钱数也就越少。我们就应该先去考虑最大金额的10元,然后顺次去考虑5元,最后就是去考虑最小金额2元,顺次遍历枚举去递增。当我们的金额与最小值相等时候就结束循环,然后将我们所需要的个数进行打印输出。
3.解题思路
3.1变量声明
首先明确我们需要三个变量,来承接我们的零钱面值。
然后明确我们需要三个变量,来作为我们的计数器,用于各个面值的遍历。
其次明确我们需要一个变量,来承接我们的遍历总钱数。
接着明确我们需要一个变量,来承接我们的商品售价。
变量声明如下:
int i,m,n; //各个面值所需个数 int a=10,b=5,c=2;//零钱面值金额 int money=69,sum;//应付金额,遍历金额
3.2金额计算与判断
最外层的i,m,n分别对应,c,b,a的个数。当我们的金额money与sum相等的时候就退出循环,并打印输出i,m,n的数值。
接下来就是我们对sum进行求解了,我们将计数器的个数乘以面值再相加就是我们的面值了。
sum =a*n+b*m+c*i; //总钱数求解 if(sum==money)break;//满足条件结束循环
(这里解释一下原因:贪心算法总是考虑局部最优解,我们这里优先考虑最大面额的零钱,所以他的循环嵌套应该是在最内层。)
3.3核心算法
这里我们使用循环来完成遍历,三个for循环进行嵌套。第一层是我们最小面值的计数,然后第二层就是我们中等面值的计数,然后最内层是我们最大面值的计数。具体原因我已经在3.2提到过了。
代码如下:
for ( i = 0; i <10;i++ ) { for ( m = 0; m<10;m++) { for ( n = 0; n < 10; n++) { sum =a*n+b*m+c*i; if(sum==money)break; } if(sum==money)break; } if(sum==money)break; else sum=0; }
4.完整代码
/* 1.我想买一本69元的图书 2.我有2元,5元,10元 3.我想要正好给他钱并且给他最少的硬币 思路: 先全用7元硬币,然后判断时候大于7如果少于则继续,如果大于则将之前的值舍去,从新分配 */ #include<stdint.h> int main(int argc, char const *argv[]) { int i,m,n; int a=10,b=5,c=2; int money=69,sum; for ( i = 0; i <10;i++ ) { for ( m = 0; m<10;m++) { for ( n = 0; n < 10; n++) { sum =a*n+b*m+c*i; if(sum==money)break; } if(sum==money)break; } if(sum==money)break; else sum=0; } printf("%d %d %d %d",i,m,n,sum);//出结果来 return 0; }
5.后记
这是一个很简单的例子,仅仅是涉及到了贪心算法的入门,在后期我将会对文章进行优化,深度挖掘贪心算法的使用场景和我们的案例分析。
6.彩蛋
多亏了我们各位聪明的小朋友,帮助小远成功买到了本子,有了这个程序小远以后再也不会被爱搞事的售货员刁难了。售货员看没有刁难到小远,含泪给小远打了对折。小远现在还在骨科挂瓶QAQ,在诊室写完了这篇文章。TAT