多个背包，重量=利润
Multiple Knapsack, weight = profit
我正在研究背包问题。现在我停在了特殊类型的多背包问题上，其中每件物品的重量等于该物品的利润。
我找不到任何关于这个问题的复杂性的论文。它是否是 NP 完全的？
如有任何帮助，我们将不胜感激。
这个问题是 NP-hard 通过减少集合分区问题。在该问题中，您将获得一组整数，并被问及是否可以将该集合分成两个总和相同的集合。您可以按如下方式将其简化为您的问题：如果该集合的总和为 2k，则创建两个容量为 k 的背包，并为要拆分的集合中的每个数字创建一个项目。然后，任何完美填充背包的方式都对应于原始集合的分区，反之亦然。 （如果数字之和不是偶数，只需将问题实例映射到背包问题的无法解决的实例）。
希望对您有所帮助！
我发现了一个可以归结为我的问题 - 多子集和问题。多子集求和问题 (MSSP) 是从给定的地面集合中选择项目并将它们打包到给定数量的相同箱中，使得每个箱中的项目权重之和不超过箱容量和总和包装物品的重量尽可能大。它可以很容易地归结为我的问题。证明我的问题是NP难的
我正在研究背包问题。现在我停在了特殊类型的多背包问题上，其中每件物品的重量等于该物品的利润。
我找不到任何关于这个问题的复杂性的论文。它是否是 NP 完全的？
如有任何帮助，我们将不胜感激。
这个问题是 NP-hard 通过减少集合分区问题。在该问题中，您将获得一组整数，并被问及是否可以将该集合分成两个总和相同的集合。您可以按如下方式将其简化为您的问题：如果该集合的总和为 2k，则创建两个容量为 k 的背包，并为要拆分的集合中的每个数字创建一个项目。然后，任何完美填充背包的方式都对应于原始集合的分区，反之亦然。 （如果数字之和不是偶数，只需将问题实例映射到背包问题的无法解决的实例）。
希望对您有所帮助！
我发现了一个可以归结为我的问题 - 多子集和问题。多子集求和问题 (MSSP) 是从给定的地面集合中选择项目并将它们打包到给定数量的相同箱中，使得每个箱中的项目权重之和不超过箱容量和总和包装物品的重量尽可能大。它可以很容易地归结为我的问题。证明我的问题是NP难的