Given an amount of sets with numbers, find a set o

问题:

Given an amount of sets with numbers (0-20 e.g) , we are asked to find the maximum set of numbers from 0-20 that doesn't include any of the given sets(it can include numbers from a set,but not the whole set) For example :Setting the max number 8 and given the sets

{1,2}
 {2,3} 
 {7}
 {3,4}
 {5,6,4},

one maximum solution is the set {1, 3, 5, 6, 8}. I was thinking of representing it as a graph and then inducting it to the Max Independent Set problem, but that seems to work only if the sets were consisted only from pairs,which doesn't stand.Any idea?Thanks in advance.

回答1:

Use a bit map for each set, setting the appropriate bit. If there are less than 32 members, you can just use a uint32_t. Full set inclusion can then be computed by masking out all members (i.e. the union of all the sets) with a specific bit map, and then using xor with the specific bit map. The result will be all 0's if a subset, otherwise the result will be a member for the Max Independent Set.