关于贪心算法

来源：10-1 贪心基础 Assign Cookies

qq_慕莱坞4316410

2023-07-14

        //对饼干大小进行排序::
        Collections.sort(s);
        //对小朋友贪心指数进行排序
        Collections.sort(i);

        int sj = s.size()-1;//指向最大的饼干
        int gi = i.size()-1;//指向最贪心的小朋友
        int rest = 0;//记录满足的个数
        while(sj >= 0 && gi >= 0){//sj 和 gi 都要大于 0 的时候
            if(s.get(sj) >= i.get(gi)){ sj--; gi--; rest++;}
            else gi--;
        }
        return rest;
    }

波波老师，这个是使用Java的从小到大解决的问题，但是老师，感觉还是对贪心算法掌握不熟练，贪心是需要先排序然后取最大和最小值这样的才是贪心算法，还是?总感觉跟着老师视频看，然后有思路能写出来，但是遇到其他算法题感觉没思路了，这种要怎么突破了，感觉没找到学习算法的方式

写回答

1回答

liuyubobobo

2023-07-15

通常一个问题，通过不断地取最大值或者最小值就能构成问题的解，就可以叫“贪心”。但其实这个定义并没有那么重要。

举个例子，比如 prim 算法是不断取出当前已经访问过的节点和没有访问节点之间的最短边，这本身是贪心，但其实你很少在算法教材中看到有人强调：prim 是个贪心算法。因为“贪心”这样一个说法的信息量太少了。直到 prim 算法使用了“贪心”的思想其实对真正理解 prim 算法的帮助没有那么大。

贪心就是一种思维方式。我么可否按照某种“序”去处理数据，进而得到问题的解。有的时候可以，有的时候不可以。但具体在一个问题中，是否可以？或者即便你知道要使用“贪心”，但是如何去具体的操作，还是相差十万八千里的，没有一定之规。（如果你没有学习图论，我告诉你求解图的最小生成树可以贪心，我相信你还是不会这个算法。）

其实很多“方法”都有类似的“性质”。

比如“反证法”，我告诉你一个数学定理能用反证法证明，不代表你就能直接证明出来。具体如何用反证法证明，很有可能完全是另一码事儿。

再比如“反差”是一种文学作品中常用的手法，但是你知道了这一点，不代表你能写出优秀的文学作品。

如何真正掌握这些方法，我不认为有任何捷径，我只有一个建议，多去接触这类方法所解决的问题。

你想更好的掌握“反证法”，多去看使用反证法可以证明的数学定理；

你想更好的掌握“运用反差的文学手法”，多去看使用这种手段的优秀的文学作品；

你想更好的掌握“贪心”，多去接触能够使用贪心解决的问题。

具体多少是“多”，每个人的基础不同，这条线会不一致，但我能肯定，对于任何人来说，个位数都肯定是不够的。

值得一提的是，我印象中我在这个课程中提及过：贪心本身就是难的（而非简单的），这是因为为什么贪心是正确的，通常背后带有非常强的数学性质。所以通常算法学到一定水平的人，都会觉得，动态规划反而是更简单的，而贪心是更难的，因为动态规划其实“套路性”更强，而“贪心”是更灵活的。

所以，如果你觉得没有彻底掌握贪心，那太正常了，因为从严格意义上讲，贪心不会被彻底掌握。贪心只是一种思维方式而已。

多去见这类问题，如果有问题随时来问答区。相信时间的力量。

加油！：）