我试图解决一个我以前没见过的背包问题。
在这个变型中，我们有一个向量V，包括每个项目的每克值，并且每个项目的权重也有限，我们的目标是找到最大值，如果我们有一组M。
我试着贪心接近，但没有找到任何解决办法。我认为最困难的部分是在O（N）中完成，因为我们不应该排序任何东西。
有人知道吗？
最佳答案
如果每克的值有相当窄的界限，你可以按每克的值对排序或基数排序或桶排序，然后按最有价值的物质的顺序填充桶。我说的合理限度是什么意思具体来说，我的意思是，每克有意义的“值”比各种物质都要少。
关于algorithm - 每个项目的值(value)和有限项目的背包问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55695606/