Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
当所有利润都等于 1 时,背包问题有一个变体。它似乎可以比经典离散 (0-1) 背包问题更快地解决,但是如何解决呢?贪心算法会起作用吗(在每次迭代中将一个重量最小的物体放在背包上)?
我应该这样认为。
直观地说,鉴于所有利润都等于 1,在利润方面,您对选择的项目无所谓,您只想要尽可能多的项目。贪心算法将为您提供准确的信息。