所有利潤等於1的揹包問題

Question

當所有利潤等於1時，存在揹包問題的變化。看起來它可以比經典離散（0-1）揹包問題快得多地解決，但是怎麼樣？只是貪心算法的工作（每次迭代都會將揹包的重量減到最小）？

Answer 1

我應該這樣認爲。

直觀地說，考慮到所有利潤都等於1，在利潤方面，您對所選擇的項目無動於衷，您只需要儘可能多。貪婪的算法會給你完全的。