HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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?

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.