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.

suggestions for reducing k and n are also welcome. The initial value for k is in the 10,000s, and the value for n is in the hundreds.

And I realized I should probably have posted this in the Posers and Puzzlers forum. Can it be moved?

What about using penalization techniques? Your problem sounds roughly like a minimax problem.