谈论贪心

2018-09-05 07:42:38来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

欢迎各位于百忙之中来看我的算法博客,这主要是为新手准备的资料,而会的大佬可以忽略。

贪心算法是一种策略算法,没有特定格式,用策略求解即可。

首先,使用贪心算法要满足该问题的局部解可以满足全局最优解。 举个栗子例子:

现在有X个包,每个包有Y种物品,每个物品的价格为z[x][y],现在从每个包里拿出N个物品,如何使总价值最大? 如: X=3,Y=2,N=1;

z[x][y]=(3 4) (5 6) (8 9)

这一题就可以采用贪心策略来解,只拿N次,将每个包的最大价值的物品取前N项。则ans=4+6+9=19;

可见贪心算法是将一个问题分解成几个小问题,再一一作答,取最优解(或较优解)。

但是有些时候,贪心不一定可以解所有问题。

如题:在一个N * M的表格中,每个格子中有一个数,每次只能向上或向右移动,求一条路径使经过点最大。

3 | 4 | 6
1 | 2 | 10

按照贪心来求为:1->3->4->6

按动态规划来求为:1->2->10->6

很明显按动规来求才是正解,故动规与贪心很容易混淆QwQ

可是如何分辨贪心与动归的区别呢?

1.手动模拟

2.猜想特殊数据

3.仔细思考

在题目中,贪心题“分糖果”比较经典

思考:

当某个孩子可以被多个糖果满足时,是否需要优先用某个糖果满足这个孩子?

当某个糖果可以满足多个孩子时,是否需要优先满足某个孩子?

贪心规律:

某个糖果如果不能满足某个孩子,则该糖果也一定不能满足需求因子更大的孩子

某个孩子可以用更小的糖果满足,则没必要用更大糖果满足,因为可以保留更大的糖果满足需求因子更大的孩子

孩子的需求因子更小则其更容易被满足,故优先从需求因子小的孩子尝试,可以得到正确的结果

所以我们可以得出思路为:先将孩子的需求量排序,在将糖果的大小排序,需求最小的孩子可以用最小的糖开始往上找,其次的孩子从上一孩子的最小需求量开始就找。

那么贪心就显得非常简单了。

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:ZR#317.【18 提高 2】A(计算几何 二分)

下一篇:算法竞赛入门经典5.1 从c到c++