Maximizing the weighted average value of a set of items by doubling the weight of a subset of items Given a set of $n$ items, each represented by $t_i=(w_i,v_i)$ for $1 \le i \le n$, the weighted average value of those items is defined as:
$$
\frac{\sum_{i=1}^{n}v_iw_i}{\sum_{i=1}^nw_i} 
$$

The goal is to find a subset of items to double their weight, such that the weighted average value is maximized. 

For example, suppose you have the following set of items, where $t_i = (w_i,v_i)$:

$$
t_1 = (12, 1100000)\\
t_2 = (12, 1000000)\\
t_3 = (12, 850000)\\
t_4 = (10, 800000) \\
t_5 = (8, 1200000) 
$$
The weighted average value is 981,481. The best solution is to double the weight of items 1 and 5, which leads to a new weighted average of 1,024,324.

I am trying to come up with an algorithm to find the best subset of items to double, and so far I've tried using bruteforce. For each item, you can choose to either double it, or leave it as it is. This means that there are a total of $2^n$ possibilities to explore, which means exponential complexity. I've also tried a greedy algorithm to pick the highest value-to-weight ratio items, and determine the best number of items to pick, however this solution is not always optimal.

I am wondering, what is the most efficient algorithm to find the best subset of items to double their weight? 

Thanks in advance.
This can be solved in polynomial time.

Hint: consider the decision version of the problem.


   Suppose I gave you a value $\alpha$ and asked you whether it's possible to find a subset of items so that the weighted average is at least $\alpha$.


Could you solve that version of the problem?  Does this give you any ideas about how to solve the original problem?



Alternate hint:


   Keep trying other greedy strategies.  You've tried one greedy algorithm, but there might be other plausible greedy algorithms.