Maximizing the boolean combination of given real numbers 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:


set $b_i=1$ if $x_i &gt; 0$
set $b_i=0$ if $x_i &lt; 0$
all others $b_i$ can either be zero or one


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).