Is this NP-Hard or does a known optimal polynomial time solution exist? [closed]

Question

Suppose we have 10 items, each of a different cost

Items: {1,2,3,4,5,6,7,8,9,10}

Cost: {2,5,1,1,5,1,1,3,4,10}

and 3 customers

{A,B,C}.

Each customer has a requirement for a set of items. He will either buy all the items in the set or none. There's just one copy of each item. For example, if

A requires {1,2,4}, Total money earned = 2+5+1= 8

B requires {2,5,10,3}, Total money earned = 5+5+10+1 = 21

C requires {3,6,7,8,9}, Total money earned = 1+1+1+3+4 = 10

So, if we sell A his items, B won't purchase from us because we don't have item 2 with us anymore. We wish to earn maximum money. By selling B, we can't sell to A and C. So, if we sell A and C, we earn 18. But just by selling B, we earn more, i.e., 21.

We thought of a bitmasking solution, which is exponential in order though and only feasible for small set of items. And other heuristic solutions which gave us non-optimal answers. But after multiple tries we couldn't really come up with any fast optimal solution.

We were wondering if this is a known problem, or similar to any problem? Or is this problem NP Hard and thus a polynomial optimal solution doesn't exist and we're trying to achieve something that's not possible?

Also, does the problem change if all the items cost the same?

Thanks a lot.

Answer 1

This problem is known as Weighted Set Packing and it is NP-complete.

In order to see this, assign each customer a set with weight which equals the sum of the item values he asks for.

The best known approximation algorithm for this problem gives a $\sqrt |\cal U|$-approximation for the optimal solution.