Finding numbers at least half the sum Let $a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n$ be positive real numbers, and $A=\sum_{i=1}^na_i, B=\sum_{i=1}^nb_i$. 
Is there an efficient algorithm (i.e. polynomial time in $n$) that finds a subset  $I$ of indices of minimum size such that $\sum_{i\in I} a_i\geq\frac{A}{2}$ and $\sum_{i\in I} b_i\geq\frac{B}{2}$?
If there were only the $a_i$'s, the problem can be solved by sorting them from largest to smallest, and greedily choosing them until their sum reaches $A/2$.
Also this could have something to do with the subset sum problem.
 A: No, there is no efficient algorithm solving your problem. Let $k$ be an integer between 1 and $\frac{n}{2}$. Then set
$$ b_i = 2A - a_i$$
for $i \leq n$ and $a_{n+1} = 0$ and
$$ b_{n+1} = 2 (n - 2k) A. $$
This implies that $B = \left(4 (n - k) - 1\right) A$.
Assume that there exists a polynomial time algorithm solving the problem with these values. Then this algorithm finds a subset $I \subseteq \{1, \ldots, n+1\}$ with
$$ \sum_{i \in I} a_i \geq \frac{A}{2} \tag{1} $$
and
$$ \sum_{i \in I} b_i \geq \frac{B}{2} = \left(2 (n - k) -\frac{1}{2}\right) A.$$
Case 1: On the one hand, if $n+1 \in I$ then this implies
$$ \sum_{i \in I \setminus \{n+1\}} 2 A - a_i = \sum_{i \in I \setminus \{n+1\}} b_i \geq \frac{B}{2} - b_{n+1} = \left(2 k - \frac{1}{2}\right) A$$
which is equivalent to
$$ \sum_{i \in I \setminus \{n+1\}} a_i \leq \frac{A}{2} + 2 (\lvert I \setminus \{n+1\} \rvert - k) A. \tag{2}  $$
In combination with (1) it must hold that $\lvert I \setminus \{n+1\} \rvert - k \geq 0$. Thus, at least $k$ elements must be chosen by the algorithm in addition to the $n+1$-th element. If it is possible to choose exactly $k$ such elements, then $\lvert I \setminus \{n+1\} \rvert - k = 0$ and (1) and (2) imply that
$$ \sum_{i \in I} a_i = \frac{A}{2}. $$
Thus, the corresponding subset sum problem has a solution.
Case 2:
On the other hand, if $n + 1 \notin I$ then
$$ \sum_{i \in I} 2A - a_i = \sum_{i \in I} b_i \geq \frac{B}{2} = \left(2(n - k) - \frac{1}{2}\right) A $$
which is equivalent to
$$ \sum_{i \in I} a_i \leq \left(2(\lvert I \rvert + k - n) - \frac{1}{2}\right) A$$
In combination with (1) it must hold that $\lvert I \rvert + k - n > 0$. This implies that
$$ \lvert I \rvert > n - k \geq \frac{n}{2} $$
since $k \leq \frac{n}{2}$. Thus, more than $\frac{n}{2}$ must be chosen in this case. Therefore, whenever only $k + 1$ elements are chosen by the algorithm we are in Case 1.
Conversely, if the subset sum problem has a solution in which $\ell$ elements are chosen, then the described problem will have a feasible solution for $k = \ell$ in which $\ell + 1$ elements are chosen including the artifitial $n+1$-th element. This solution can be found by trying all values of $k = 1, \ldots, \frac{n}{2}$ and checking if the solution provided by the algorithm chooses only $k+1$ elements.
Therefore, any algorithm solving your problem in polynomial time would also solve the subset sum problem in polynomial time. This is not possible unless P = NP.
