问：关于特化 01 背包

学术版

Jerrycyx @ 2024-11-29 15:02:11

所有物品的价值都为 2，另外还有最多两个物品的价值为 1，这样可以在 O(N) 或 O(N \log N) 的时间复杂度求解吗？

感觉其实更像是贪心而不是背包动态规划。求大佬解答！

by liangbowen @ 2024-11-29 15:03:45

你直接枚举那两个物品选不选，其他的贪心呗

by _czy @ 2024-11-29 15:04:21

显然排序即可

by CJ07 @ 2024-11-29 15:04:49

@Jerrycyx 价值为相同重量从小到大选。枚举价值为 1 的物品选几个即可。

by Jerrycyx @ 2024-11-29 15:06:29

@liangbowen @_czy @CJ07 感谢！

by chen_z @ 2024-11-29 15:07:21

@Jerrycyx 枚举那两个物品选不选，其他贪心即可。

有序的话就是 O(n)

|