-3

We are given N fruits and M choices to select those fruits.M lines have some integers and the first one is K and each M lines follows K integers after the first value (ie. K) denoting the indices of fruit to be selected in that choice. I need to find out the maximal number of choices that can be selected.

Note :- There is only one fruit at a particular index.

Sample Input:-

4 3

2 1 2

2 2 3

2 3 4

Output :-

2

As we can select 1st and 3rd choice.

Which Algorithm should I use to solve this question ?

kvnt1102
  • 1
  • 2
  • This is obviously Homework. Any attempt to share ? Any knowledge about graph theory ? – hivert Mar 10 '14 at 14:13
  • Duplicate of http://stackoverflow.com/questions/22272445/how-to-code-the-maximum-set-packing-algorithm/22275179#22275179 – hivert Mar 10 '14 at 14:15

2 Answers2

0

This is a variation of the maximum independent set

There are very well detailed algorithms for finding maximum independent set in this paper: Algorithms for Maximum independent Sets

And a parallel approach has been provided in this one:Lecture Notes on a Parallel Algorithm for Generating a Maximal Independent Set

And this is a java implementation.

Mohsen Kamrani
  • 7,177
  • 5
  • 42
  • 66
0

This is the set packing problem, one of the classic NP-complete problems. There is no efficient solution, but you can try a backtracking algorithm (slow but exact) or a greedy approximation (fast but suboptimal).

user2357112
  • 260,549
  • 28
  • 431
  • 505