patternMinor
Find non-overlapping subsets that maximize the sum of their values
Viewed 0 times
sumthenonsubsetsoverlappingthatmaximizefindvaluestheir
Problem
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?
Has this problem already been studied somewhere, or is it linked to some well-known optimization problem?
Solution
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.
Context
StackExchange Computer Science Q#78147, answer score: 2
Revisions (0)
No revisions yet.