Maximizing the weighted average value of a set of items by doubling the weight of a subset of items
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.