这是NP-Hard还是存在已知的最优多项式时间解？

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

因此,如果我们出售他的物品,B将不会向我们购买,因为我们不再拥有第2项物品.我们希望赚到最多的钱.通过卖B,我们不能卖给A和C.所以,如果我们卖A和C,我们赚18.但只要卖B,我们赚的更多,即21.

我们想到了一个位掩码解决方案,它按顺序呈指数级,但只适用于少量项目.和其他启发式解决方案给了我们非最佳答案.但经过多次尝试后,我们无法真正提出任何快速优化解决方案.

我们想知道这是一个已知问题,还是类似于任何问题？或者这个问题是NP Hard,因此多项式最优解不存在,我们试图实现一些不可能的事情？

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

非常感谢.

Answer 1

这是(加权)集合包装问题,是卡普21个原始NP难问题之一.未加权的版本也是NP难的.如果你试图在实践中有效地解决它,一个合理的方法是将以下整数程序公式(从维基百科)提供给求解器.让我们x_i = 1,如果我们满足客户i,让x_i = 0如果我们不满足客户i.

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}