[已解决]贪心算法详细讲解

zhangjinxuan · 发表于 2023-7-27 20:26:12

贪心不证明，爆零两行泪。

zhangjinxuan · 发表于 2023-7-27 20:28:36

比方说，你要从 n 个数字里面选择 m 个数字，要让数字之和最大。

贪心流程：从大到小选择数字。
证明：若不从大到小选择，则目前选择的数字一定小于剩余未选择数字的其中一个或一些，那么累加起来的和就一定不是最优的一个解。

zhangjinxuan · 发表于 2023-7-27 20:31:05

我没看帖子内容，看了一下，这道题应该要用 LIS 来做，LIS 是一道 DP 的题目，但时间复杂度 O(N^2)，因此需要贪心来优化。

具体怎么贪心，我看你贪心是处于入门的水平，目前学习 LIS 可能会有点困难，但是如果你还是要学的话我可以给你一些参考。

zhangjinxuan · 发表于 2023-7-27 20:32:25

Ewan-Ahiouy 发表于 2023-7-27 20:29
http://w466763.s144.myverydz.cn/forum.php?mod=viewthread&tid=19&extra= 元豪写的

原来你也知道梦想论坛

zhangjinxuan · 发表于 2023-7-27 21:03:07

tommyyu 发表于 2023-7-27 21:00
01背包用贪心是个好主意我们只需要每次挑一个价值最大的就可以了这题也是一样，直 ...

《别怪我》

账号		自动登录	找回密码
密码			立即注册