CODEWITHSUNDEEP
algorithmcomplexity-theory
Hoxeni
Hoxeni

Reputation: 157

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

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.

Upvotes: 3

Views: 108

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65447

This is the (weighted) set packing problem, one of Karp's 21 original NP-hard problems. The unweighted version also is NP-hard. If you're trying to solve it efficiently in practice, a reasonable approach is to feed the following integer program formulation (from Wikipedia) to a solver. Let x_i = 1 if we satisfy customer i and let x_i = 0 if we don't satisfy customer 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}

Upvotes: 6

Related Questions