这个问题是NP难问题还是已知存在多项式时间最优解？

Question

假设我们有10个不同成本的项目：

项目：{1,2,3,4,5,6,7,8,9,10}

成本：{2,5,1,1,5,1,1,3,4,10}

还有3个客户：

{A,B,C}。

每个客户都有一组需求项目。他要么购买集合中的所有项目，要么不购买。每种项目只有一个副本。

例如，如果:

A需要 {1,2,4}，总收入= 2+5+1= 8

B需要 {2,5,10,3}，总收入= 5+5+10+1= 21

C需要 {3,6,7,8,9}，总收入= 1+1+1+3+4= 10

因此，如果我们向A销售他需要的项目，B将不会从我们这里购买，因为我们没有项目2了。我们希望获得最大收益。通过向B销售，我们无法向A和C销售。因此，如果我们向A和C销售，我们可以获得18元收益。但是仅通过向B销售，我们可以获得更多的收益，即21元。

我们考虑了一种位掩码解决方案，但它的阶数是指数级的，只适用于小型项目集。其他启发式解决方案给出了非最优答案。但在多次尝试后，我们无法想出任何快速的最优解决方案。

我们想知道这是否是一个已知问题或类似的问题？或者这个问题是NP困难问题，因此不存在多项式最优解决方案，我们正试图实现不可能实现的东西？

另外，如果所有项目的成本相同，问题是否会改变？

谢谢。

- Hoxeni

---

标题中的问题有点错误：NP难问题可能存在已知的最优解。 - kviiri

可能更适合于http://cstheory.stackexchange.com/。 - NPE

@kviiri 好的..谢谢。 :) 现在听起来更好了吗？ - Hoxeni

@NPE 我也会在那里发布。谢谢 :) - Hoxeni

这不是研究级别的问题。我会在这里回答。 - David Eisenstat

Answer 1

这是（加权的）集合覆盖问题，是 Karp 的 21 个原始 NP 难题之一。未加权版本也是 NP 难的。如果你想在实践中高效地解决它，一个合理的方法是将以下整数规划公式（来自维基百科）输入求解器。如果我们满足客户 i，则让 x_i = 1，如果我们不满足客户 i，则让 x_i = 0。

maximize sum_{customers i} (profit from selling to i) * x_i
subject to
for all items j, sum_{customers i desiring j} x_i <= 1
for all customers i, x_i in {0, 1}

- David Eisenstat