每件物品和有限物品的背包问题

Question

我正在尝试解决以前从未见过的背包问题变体。 在这个变体中，我们有一个向量 v，其中包含每个项目的每克值，并且每个项目的重量也有限，我们的目标是找到如果我们有一包大小为 M 的情况下可以获得的最大值。 我尝试贪婪地接近但没有找到任何解决方案。我认为最困难的部分是在 O(n) 中完成，因为我们不应该对任何东西进行排序。 有人知道吗？

Answer 1

如果每克的价值有相当窄的界限，你可以在线性时间内按每克的价值进行计数排序或基数排序或桶排序，然后按最有价值的顺序填满桶物质。我所说的合理限制是什么意思？具体来说，我的意思是有意义的 "values per gram" 渐近地少于物质的种类。