Maximizing the boolean combination of given real numbers

Question

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.

Answer 1

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 > 0$
• set $b_i=0$ if $x_i < 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).