I have come across the following problem but am unable to understand the solution for it. Hence I would like to know if it has a formal name then, I can search for it and read about it in more detail. Also it will help me ask better questions about it in such forums.

Problem Statement: Given $n$ objects and two lists $V_n = \{v_1,v_2,\dots,v_n\}$ and $W_n=\{w_1,w_2,\dots,w_n\}$, where $V_n$ denotes the value for a particular item and $W_n$ denotes the weight for a particular item.

Pick $k$ items so that the following ratio is maximized:

$$\frac{\sum_{j=1}^{k}{v_{i_j}}}{\sum_{j=1}^{k}{w_{i_j}}} $$

I have seen the solutions but I am unable to fully understand them correctly. I have head that this problem was invented in 2005.

So does have some sort of a formal name ?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.