赞
踩
1.题目:柠檬水找零
在柠檬水摊上,每一杯柠檬水的售价为5美元。顾客排队购买你的产品,一次购买一杯。
每位顾客只买一杯柠檬水,然后向你付5美元、10美元或20美元。必须给每个顾客正确找零
注意,一开始你手头没有任何零钱。
如果你能给每位顾客正确找零,返回 true ,否则返回false,
2.算法:
1.贪心算法
3.算法思想
贪心算法:
1.解决思路
5元直接收下 ,一种情况 ,
10元,需要看有没有 5元的存储,有的话 5元出去 一个单位,进来一个 10元单位,一种情况
20元 两种情况, 一个是 一个 5元 + 一个 10 元, 第二种是 3个 5元
所以在这种情况下 5 元是万能的使用单位,所以5元 我们需要最后用!
代码:
- /*************************************************
- 作者:She001
- 时间:2022/8/31
- 题目:柠檬水找零
- 在柠檬水摊上,每一杯柠檬水的售价为5美元。顾客排队购买你的产品,一次购买一杯。
- 每位顾客只买一杯柠檬水,然后向你付5美元、10美元或20美元。必须给每个顾客正确找零
- 注意,一开始你手头没有任何零钱。
- 如果你能给每位顾客正确找零,返回 true ,否则返回false,
-
- 算法:
- 1. 贪心算法
-
- ***************************************************/
-
- #include<bits/stdc++.h>
- using namespace std;
-
-
- /*
- 贪心算法:
- 1.解决思路 5元直接收下 ,一种情况 , 10元,需要看有没有 5元的存储,有的话 5元出去 一个单位,进来一个 10元单位,一种情况
- 20元 两种情况, 一个是 一个 5元 + 一个 10 元, 第二种是 3个 5元 //所以在这种情况下 5 元是万能的使用单位,所以5元 我们需要最后用!
-
- */
- bool fangfa_1(int num[],int n)//num 数组 ,n 数组的元素个数
- {
- int five=0; //5元 的个数
- int ten=0; //10元 的个数
- for(int i=0;i<n;i++)
- {
- if(num[i]==5)
- {
- five++;
- }
- else if(num[i]==10)
- {
- if(five<1)
- {
- return false;
- }
- five--;
- ten++;
- }
- else if(num[i]==20)
- {
- if(ten>1&&five>1)
- {
- ten--;
- five--;
- }
- else if(five>=3)
- {
- five-=3;
- }
- else
- {
- return false;
- }
- }
- }
- return true;
- }
-
- int main()
- {
- int num[]={5,10,5,5,5};
- int a=fangfa_1(num,5);
- if(a==0)
- {
- cout<<"false"<<endl;
- }
- else
- {
- cout<<"true"<<endl;
- }
- return 0;
- }
贪心算法(greedy algorithm [8] ,又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解 。
贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择 。
①建立数学模型来描述问题 。
②把求解的问题分成若干个子问题 。
③对每个子问题求解,得到子问题的局部最优解 。
④把子问题的解局部最优解合成原来解问题的一个解 。
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择,就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪心算法不要回溯 。
1、有一个以最优方式来解决的问题。为了构造问题的解决方案,有一个候选的对象的集合:比如不同面值的硬币 [3] 。
2、随着算法的进行,将积累起其他两个集合:一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象 [3] 。
3、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优 [3] 。
4、还有一个函数检查是否一个候选对象的集合是可行的,即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性 [3] 。
5、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解 [3] 。
6、最后,目标函数给出解的值 [3] 。
1、贪心选择性质
一个问题的整体最优解可通过一系列局部的最优解的选择达到,并且每次的选择可以依赖以前作出的选择,但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解 [4] 。
2、最优子结构性质
当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中,至于什么问题具有什么样的贪心选择性质是不确定的,需要具体问题具体分析
贪心算法不从整体最优上加以考虑,所做出的仅是在某种意义上的局部最优选择。使用贪心策略要注意局部最优与全局最优的关系,选择当前的局部最优并不一定能推导出问题的全局最优。贪心策略解题需要解决以下两个问题:
1、该问题是否适合使用贪心策略求解,也就是该问题是否具有贪心选择性质 ;
2、制定贪心策略,以达到问题的最优解或较优解 。
要确定一个问题是否适合用贪心算法求解,必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为:首先考察问题的一个整体最优解,并证明可修改这个最优解,使其以贪心选择开始,做了贪心选择后,原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择,最终可得到问题的整体最优解 。
编辑 播报
1、不能保证解是最佳的。因为贪心算法总是从局部出发,并没从整体考虑 ;
2、贪心算法一般用来解决求最大或最小解 ;
3、贪心算法只能确定某些问题的可行性范围;
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。