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


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.

  • $\begingroup$ This is likely not a research level question and is cross-posted to computer science against our policies, so I'm closing it here. $\endgroup$ – Lev Reyzin Aug 21 '14 at 20:13

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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.