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.


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.