0
$\begingroup$

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.

$\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.