所有利润等于 1 的背包问题

Question

当所有利润都等于 1 时，背包问题有一个变体。看起来它可以比经典离散 (0-1) 背包问题更快地解决，但是如何解决呢？贪婪算法会起作用吗（在每次迭代中将重量最小的物体放入背包中）？

Answer 1

我应该这么认为。

直观上，考虑到所有利润都等于 1，在利润方面，您对选择哪些项目并不关心，您只想要尽可能多的项目。贪心算法会给你准确的结果。