谈论贪心

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

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

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

现在有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
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有