<p>I have a number of sets, each containing items with a numerical value and a string.</p>

<p>I want to choose one item out of each set, so that:
1. the strings of the chosen items form a set (i.e. the strings are not equal to any of the strings from the other chosen items)
2. the numerical values of the chosen items are as high as possible</p>

<p>It is not always possible to satisfy 1., e.g. two sets may contain only one item each, both with the same string. When not possible to satisfy 1., the optimal solution is the one that is closest to satisfy 1., 2. is not as important.</p>

<p>How do I find the optimal solution? Are there any widely known algorithms for performing this or something similar?</p>

CC BY-SA 3.0
2011-06-28T14:40:59.593Z
Looks like a [maximum weighted bipartite matching problem](http://en.wikipedia.org/wiki/Hungarian_algorithm).
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-06-30T17:26:32.923Z
@張顯之 : That would be true if the sets were singletons.  This looks more complicated.
Pat Morin
CC BY-SA 3.0
2011-07-04T16:27:41.967Z
@Pat: To me it looks exactly like max-weight bipartite matching. Left part: sets; right part: strings; there is an edge of weight $w$ between set $S$ and string $x$ if there is pair $(w,x)$ in set $S$. A matching chooses at most one string from each set, and no string is chosen twice.
Jukka Suomela
CC BY-SA 3.0
2011-07-05T07:39:47.367Z
It is not very important in my application. But I would say that a higher grand total is better.
Jonatan Kallus
<ds.algorithms><graph-algorithms>
Algorithm for choosing unique items from a collection of sets of items
Jonatan Kallus
# Algorithm for choosing unique items from a collection of sets of items

(Asked by: username_0 on 2011-06-28)

I have a number of sets, each containing items with a numerical value and a string.

I want to choose one item out of each set, so that:
1. the strings of the chosen items form a set (i.e. the strings are not equal to any of the strings from the other chosen items)
2. the numerical values of the chosen items are as high as possible

It is not always possible to satisfy 1., e.g. two sets may contain only one item each, both with the same string. When not possible to satisfy 1., the optimal solution is the one that is closest to satisfy 1., 2. is not as important.

How do I find the optimal solution? Are there any widely known algorithms for performing this or something similar?

**Tags:** ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: Looks like a [maximum weighted bipartite matching problem](http://en.wikipedia.org/wiki/Hungarian_algorithm).  
> **username_2**: @張顯之 : That would be true if the sets were singletons.  This looks more complicated.  
> **username_3**: @Pat: To me it looks exactly like max-weight bipartite matching. Left part: sets; right part: strings; there is an edge of weight $w$ between set $S$ and string $x$ if there is pair $(w,x)$ in set $S$. A matching chooses at most one string from each set, and no string is chosen twice.  
> **username_0**: It is not very important in my application. But I would say that a higher grand total is better.  

---

## 0 answers

