一坨鸡矢
by _Karasu_ @ 2022-08-08 02:24:53
@[qibaoan8](/user/764241) tjqtj,bkpy,[xyhbd](https://www.luogu.com.cn/discuss/241461)
by Gumbo @ 2022-08-08 06:52:17
跟这没关系吧。你这是贪心，但背包本质是 DP。
by 伟大的王夫子 @ 2022-08-08 08:26:33
@[伟大的王夫子](/user/162196) 感谢大佬回复，我是刚刚注册洛谷，本来想的是看懂之后随手发帖记录下，没想到有大佬能回复。
我是近期刚学贪心算法和动态规划，理解的还没有那么透彻，希望多多指点。
我理解如下：
贪心算法：通常是以较低复杂度做到当前局部最优，单结果未必是全局最优；
动态规划：通过数组记录每个阶段最优的结果，遍历完所有的场景保证全局最优，复杂度较高；
我上面举例说的把价值低的物品“扔了”也不是真扔了，而是通过dp的二维数组记录下来，当包裹空间放大到能装下这个物品时，再重新装进来，当有新物品出现时再重新对比新物品会不会比包裹里面的更有价值，一直到遍历完最后一个物品，算出最终的最高价值。这应该算是动态规划的解题思路吧？
by qibaoan8 @ 2022-08-08 14:39:04
我的理解是：
贪心：每次根据局部最优决策进行决策。
动态规划：定义状态，并且通过子状态推出大状态。
by 伟大的王夫子 @ 2022-08-08 17:24:03
@[_Karasu_](/user/123451)
哈哈哈笑死阿（……）好好笑这句话哈哈哈不知道为什么
by Tzj123_ORZ @ 2022-08-13 11:41:24
话说帖子也不是给你随手记录自己想法的地方啊
by 云雷心柠檬听 @ 2022-08-13 21:43:34