芜湖做网站都有哪些,广州音乐制作公司,网络推广公司名字,seo电商运营是什么意思一、算法内容
1.简介
贪心算法是指在对问题求解时#xff0c;总是做出在当前看来是最好的选择#xff0c;而不考虑后续可能造成的影响。也就是说#xff0c;不从整体最优上加以考虑#xff0c;只做出在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优…一、算法内容
1.简介
贪心算法是指在对问题求解时总是做出在当前看来是最好的选择而不考虑后续可能造成的影响。也就是说不从整体最优上加以考虑只做出在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解关键是贪心策略的选择选择的贪心策略必须具备无后效性即某个状态以前的过程不会影响以后的状态只与当前状态有关。
在贪心算法的应用当中往往都会和排序联系起来所以想要熟练使用贪心算法则必须首先能够熟练地应用排序。而由于贪心算法采取的是局部最优策略故如果使用贪心算法之前往往需要证明算法的正确性即证明在此题目/事件中在每一步采取局部最优策略会得到整体最优的结果。
2.对比与联系
与此算法相对应的是后续我们会学到的动态规划在动态规划中我们则必须要考虑一个选择对后续的影响。
贪心算法的应用非常广泛很多其他的算法都需要贪心算法来作为基础。例如哈夫曼编码、 K r u s k a l Kruskal Kruskal算法、 P r i m Prim Prim算法、 A ∗ A^* A∗算法等等。所以学好贪心算法是非常重要。
二、实例分析
1.最简单的例子
下面我们将以洛谷上的题目P1208为例讲解贪心算法的最简单的使用方式。
1题目大意
公司需要收购一定量的牛奶每一个奶农能卖出的牛奶的量和价格都不同公司希望能以最少的钱买到足够量的牛奶
2题目分析
显然按照题目意思我们只需要将牛奶价格排序好然后从价格低的开始买如果此价格的牛奶已经没了那么才购买价格更高的牛奶一直买到满足公司收购的量为止即可。
本题目的贪心非常浅显易懂这里不再给出证明。
3正解程序
#include iostream
#include cstring
#include cmath
#include algorithm
#include cstdlib
#include cstdiousing namespace std;
typedef long long ll;
const ll maxn5010;
ll n,m,ans0;
struct node
{ll per,num;
}farmer[maxn];
bool cmp(node x,node y)
{if(x.per!y.per)return x.pery.per;elsereturn x.numy.num;
}
int main()
{scanf(%lld%lld,n,m);for(ll i1;im;i)scanf(%lld%lld,farmer[i].per,farmer[i].num);sort(farmer1,farmer1m,cmp);ll pos1;while(n){if(farmer[pos].num!0){farmer[pos].num--;ansfarmer[pos].per;n--;}elsepos;}printf(%lld\n,ans);return 0;
}2.稍微复杂一点的例子
下面我们将以洛谷上的题目P1094为例讲解贪心算法的进一步应用并给出证明的思路。
1题目大意
有一组物品需要进行分组每个物品都有一个价格希望保证每一组的价格总和小于某一固定值的情况下使得分组数尽量小每一组最多包含两个物品
2题目分析
首先我们能够想到要使分组数尽可能小那么一定是尽量两两组合所以我们很容易能够想到一个贪心思路那就是将物品按价格从小到大排序然后尽量用价格小的和价格大的进行组合。可以提前说明的是这个贪心思路是正确的然而问题并没有完全解决为什么这样组合之后就能使得最后的分组数最小呢
3贪心证明 根据我们前面所讲到的点将使用反证法证明 设价格总和上限为 X X X现有四个物品的价格为 v a , v b , v c , v d v_a,v_b,v_c,v_d va,vb,vc,vd按从小到大排序 若 v a v d ≤ X , v b v c ≤ X v_av_d\leq X,v_bv_c\leq X vavd≤X,vbvc≤X此为贪心法得到的分组最少分为两组。下面改变组合方式因为 v a v c ≤ X v_av_c\leq X vavc≤X显然成立所以仅考虑另一组的情况。 若 v b v d ≤ X v_bv_d\leq X vbvd≤X那么可以分为两组若 v b v d ≤ X v_bv_d\leq X vbvd≤X那么仅能分为一组。因为 v a ≤ v b v_a\leq v_b va≤vb所以此处情况完全可能出现。 若 v a v d X v_av_d X vavdX则无论如何都只能分为一组 若 v a v d ≤ X , v b v c X v_av_d\leq X,v_bv_c X vavd≤X,vbvcX。下面考虑 v a v c , v b c d v_av_c,v_bc_d vavc,vbcd这一种组合方式显然 v b v d X v_bv_dX vbvdX所以无论怎么分仍然只有一组。 可以看到非贪心的情况有可能导致答案数变少。例如 v a 1 , v b 5 , v c 6 , v d 8 , X 11 v_a1,v_b5,v_c6,v_d8,X11 va1,vb5,vc6,vd8,X11
4正解程序
#include iostream
#include cstring
#include cmath
#include algorithm
#include cstdlib
#include cstdiousing namespace std;
typedef long long ll;
const ll maxn1000010;
ll num[maxn],ans;
int main()
{ll n,w;scanf(%lld%lld,w,n);for(ll i0;in;i)scanf(%lld,num[i]);sort(num,numn);ll z0,yn-1;while(zy){if(num[z]num[y]w){ans;z;y--;}else{y--;ans;}}printf(%lld\n,ans);return 0;
}三、作业
1.基础题
P1094 [NOIP2007 普及组] 纪念品分组
P1208 [USACO1.3]混合牛奶 Mixing Milk
P3817 小A的糖果
P5019 [NOIP2018 提高组] 铺设道路
2.提高题
P1056 [NOIP2008 普及组] 排座椅
P1199 [NOIP2010 普及组] 三国游戏
