Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Let $x_1, x_2, \dots, x_n \in \mathbb R$ and $b_1, b_2, \dots, b_n \in \{0,1\}$. I want to know which of all the possible boolean combinations is maximal. For example, if $x_1 = 2$ and $x_2 = -2$,
$$\max \sum_i b_i x_i = 2 \implies b_1 = 1, b_2 = 0$$
I can see that a brute force algorithm will have a running time complexity of $O(2^n)$. My question is whether there is an efficient algorithm for this or, at least, an approximation algorithm.
Maybe there is something I do not understand in your question, but the way it is formulated it seems that the set of solutions is:
It is clear that any other assignment will give you a lower value (either by adding a positive value or not adding a positive one). If $|\{i:x_i=0\}|=K$, then you have $2^K$ solutions. This can be settled in $O(n)$ by a simple linear scanning of $x_i$ values (even less if they are ordered).
