0
$\begingroup$

I am considering a variant of the classical fractional knapsack problem, it's written in the following integer programming form IP formulation

Here $v_i, c_i, w_i, b$ are all positive. $c_i$ can be interpreted as the setup cost for selecting item $i$. Clearly if we know the optimal $x_i$ for all items, then the problem reduces to a simple fractional knapsack problem which can be solved in linear time. But my question is if there is a clever way to find the optimal solution using dynamic programming.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.