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

Question

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

Answer 1

我应该这样认为。

直观地说，鉴于所有利润都等于 1，在利润方面，您对选择的项目无所谓，您只想要尽可能多的项目。贪心算法将为您提供准确的信息。