# Knapsack-type problem where the objective function is a ratio

I have a problem where I have a number of proposed initiatives each with a cost and payoff. I need to select a subset of these initiatives in order to maximize the ROI for the selected set as a whole while staying within a total cost constraint. Specifically, the problem is:

Maximize [sum(v_i*x_i)/sum(c_i*x_i)]
Subject to sum(c_i*x_i) <= C and x in {0,1}
Where v_i = payoff from initiative i, c_i = cost of initiative i, and x_i = 0/1 decision to select investment i or not


I understand that if the objective function in such a problem is just a sum then it is a 0/1 knapsack problem. If the function is a ratio as in this case, is there a specific name for this kind of a problem, or a recommended algorithm for solving it?

• Are the costs integers? About how large is $C$? About how large is the typical $c_i$? – D.W. Sep 15 '18 at 15:28

Do the regular dynamic programming approach to solve simply maximizing $\sum v_ix_i$. In that approach you end up with an array $m[i, c]$ which is the maximum value you can reach with cost less than or equal to $c$ using items up to $i$.
Then simply do a $O(C)$ loop to find the best possible $\frac{m[n, c]}c$ for each $c$ where $n$ is the number of items.
• Nice! Caveat: this works if the $c_i$'s are integers and $C$ is not too large*, but not if the $c_i$'s are continuous/real numbers or if $C$ is super-large (though still it's possible to use this method to get an approximation, as in en.wikipedia.org/wiki/…). – D.W. Sep 15 '18 at 15:30