如果你有一个二进制背包问题，所有物品的密度(值/体积)都相同，你会怎么解决

Question

正如标题所问，不确定是使用基于体积的贪婪方法，还是使用NP完全方法。

Answer 1

所有物品密度相同的二进制背包问题本质上等价于子集和问题。在这个问题中，你得到了一组自然数S和一个目标数k，并被要求确定它是否有一个和恰好为k的子集。你可以通过将S中的每个数映射到一个权重和值相同的项来轻松地将子集和简化为你的问题。既然子集和问题是NP完全的，那么你的问题也是。