# Find non-overlapping subsets that maximize the sum of their values

Given a set of elements $N$, a set $S$ of subsets of $N$, and a function $v:S \to \mathbb R$, determine a set $R\subseteq S$ of non-overlapping subsets that maximizes the total value.

Has this problem already been studied somewhere, or is it linked to some well-known optimization problem?

• Is the function $v$ positive valued? Jul 20 '17 at 21:48
• No, it is not positive valued. Jul 21 '17 at 6:25

Yes this problem has already been studied. It is a well-known $NP$-complete problem known as Set-Packing. Your problem is a weighted optimization variation, but the same principles apply.
• I see. Basically set packing is a special case of this problem, with $v(\cdot)=1$ for all subsets. Jul 21 '17 at 6:31
You can reduce it to the following graph theoretic problem, but I don't know if it is in $P$.
Denote each set in $S$ as a vertex and give it a weight $f(S)$, in other words your vertices are weighted. Then if two sets are overlapping connect them by and edge. Then you have to find a subset $V'$ of vertices such that if $v,u \in V'$ then $(u,v) \notin E$, that is they are not adjacent to each other and sum of weights of vertices in $V'$ have to be maximal.