PROBLEM LINK:
Author: Akul Sareen
Tester: Tapan Sahni
Editorialist: Akul Sareen
DIFFICULTY:
MEDIUM
PREREQUISITES:
Binary search, Greedy
PROBLEM:
Given N items, each with an associated weight and value, choose exactly M items such that the ratio of sum of value to sum of weight of chosen items is maximum
QUICK EXPLANATION:
Binary search for the maximum ratio. While checking for a given ratio R greedily picking items with maximum value - R*weight is sufficient.
EXPLANATION:
The sample cases might lead you to believe that greedily picking items based on their value to weight ratio should get the right answer. However, that is not correct. Consider the case where there are 3 items with (value,weight) = (4,1),(4,3),(1,1) and you have to pick 2 items. Greedy will get you a value to weight ratio = 8/4 = 2, whereas the actual answer will get you 5/2 = 2.5.
As with many questions that ask you to maximize or minimize a value, you can try binary searching for the answer. To be able to do that we need to be able to answer the question, whether for some ratio R it is possible to achieve that ratio. Therefore, we want to find some set of M items such that:
$\displaystyle \frac{val_1 + val_2 + \dots + val_m}{wt_1 + wt2 + \dots + wt_m} \geq R $then, we can rearrange the inequality to get:
$(val_1 - R \times wt_1) + (val_2 - R \times wt_2) + \dots + (val_m - R \times wt_m) \geq 0$Let x_i = val_i - R \times wt_i, then for some given R we are simply trying to find a set of M items such that x_1 + x_2 + \dots + x_m \geq 0. We can do this step greedily by taking the M items with the largest values of x. If their sum is less than 0, then <b<R cannot be achieved, else it can.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution will be uploaded later.