Q:

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?

A:

I can't refer you to literature on this subject, but I did come up with a strategy to solve it.
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.

