I have a minimization problem I need to solve as accurately as possible. I think it's NP-complete, but not entirely sure. I'd like to know if anyone has better ideas for solving it than I have, since my solution is O(2^n) time, and that's not acceptable.
I have n vectors, each of which can be represented with a k-bit binary number. Each vector has a "weight" of w
I need to select vectors such that the result of an AND between all of the vectors meets a maximum density (there is a max number of 1's in the result) while minimizing w.
The ideal solution would be to build a binary tree of the vectors such that each leaf represents one possibility of included/excluded vectors and the sum of w for the included vectors. The problem is that building this binary tree takes O(2^n) time.
Is there some way to combine the density of each vector with its weight to come up with a combined ranking of each vector? Feel free to ask for clarification if the problem is unclear.