Suppose I have $n$ items, each with value $v(j)$ and weight $w(j)$, and $m$ knapsacks each with capacity $c(i)$. If I make the assumption that $w(j-1)$ evenly divides $w(j)$, then there's a nice optimal packing algorithm outlined in Detti, A polynomial algorithm for the multiple knapsack problem with divisible item sizes.

I have a slight variant to this problem, where the value depends on the knapsack I put the item in: $v(j,i)$. Is there any paper or book detailing an exact optimal solution to this problem? In my case $v(j,i)$ takes at most 2 distinct values, but I'm not sure if that matters.


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.