Given N number of bitsets consisting of M bits, choose K bitsets such that there is no multiple 1s occurring in the same position. What is the maximum number of 1s that can be formed?
Example:
N = 5, M = 6
001100
011010
100100
111001
001010
The answer would be combining 011010 and 100100, where the answer is 5.
I expect a polynomial time solution, although I am not sure whether it is possible. The problem is taken from here with probably better phrasing.
This is weighted maximum set packing where each bitset is interpreted as a set, and the weight of each set is its cardinality.