<p>This problem is known as <a href="http://en.wikipedia.org/wiki/Set_packing#Weighted_version" rel="nofollow">Weighted Set Packing</a> and it is NP-complete.</p>

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

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

CC BY-SA 3.0
2014-08-20T14:50:51.013Z
2014-08-20T14:50:51.013Z
R B
<p>Suppose we have 10 items, each of a different cost </p>

<blockquote>
  <p>Items:    {1,2,3,4,5,6,7,8,9,10} </p>
  
  <p>Cost:     {2,5,1,1,5,1,1,3,4,10}</p>
</blockquote>

<p>and 3 customers </p>

<blockquote>
  <p>{A,B,C}.</p>
</blockquote>

<p>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 </p>

<blockquote>
  <p>A requires {1,2,4}, Total money earned = 2+5+1= 8</p>
  
  <p>B requires {2,5,10,3}, Total money earned = 5+5+10+1 = 21</p>
  
  <p>C requires {3,6,7,8,9}, Total money earned = 1+1+1+3+4 = 10</p>
</blockquote>

<p>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.</p>

<p>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.</p>

<p>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?</p>

<p>Also, does the problem change if all the items cost the same?</p>

<p>Thanks a lot.</p>

CC BY-SA 3.0
2014-08-21T20:13:05.320Z
This is likely not a research level question and is cross-posted to computer science against our policies, so I'm closing it here.
Lev Reyzin
<cc.complexity-theory><ds.algorithms><heuristics>
Is this NP-Hard or does a known optimal polynomial time solution exist?
Hoxeni
# Is this NP-Hard or does a known optimal polynomial time solution exist?

(Asked by: username_0 on 2014-08-20)

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.

**Tags:** cc.complexity-theory, ds.algorithms, heuristics

> **Comments:**
> **username_1**: This is likely not a research level question and is cross-posted to computer science against our policies, so I'm closing it here.  

---

## 1 answers

### Answer by username_2 on 2014-08-20. Score: 3

This problem is known as [Weighted Set Packing](http://en.wikipedia.org/wiki/Set_packing#Weighted_version) 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.


---

