# Multi- Knapsack problem variation

I'm trying to model a scenario where there are n items, each having weight and volume. We also have m number of knapsack, each having a weight and volume capacity, where these items need to go inside. A feature that I am looking for is that the value property of each item which depends on which knapsack it goes into. For instance, item 1 has value of v1 if goes into knapsack 1, and v2 if it goes to knapsack 2.

How can I model the problem as a knapsack and an optimization problem so to maximize the overall value? So far I came into a multiple knapsack problem, 2 dimensional. For for the value, I don't have any clue.

## 1 Answer

The simplest approach is to formulate this as an instance of integer lienar programming. You have zero-or-one variables $x_{i,j}$, where $x_{i,j}=1$ means that item $i$ is placed into knapsack $j$. Then all of your constraints can be straightforwardly expressed as linear inequalities on these variables.

• Just a resource: or.deis.unibo.it/kp/Chapter6.pdf – fade2black Sep 13 '17 at 15:59
• I'm more of a KP guy. I have seen many cases where both KP and LP were both used. Any insights on KP formulations? – Tina J Sep 13 '17 at 16:19
• @TinaJ, what's KP? What is a KP formulation? – D.W. Sep 13 '17 at 19:34
• Knapsack Problem. I was wondering if we can map it into a known variation of knapsack. – Tina J Sep 13 '17 at 21:34
• @fade2black thats a terrible resource. You have to start reading that book from the start to understand what they are on about by chapter 6. Also, its heavily academic with a focus on complexity theory. There seems to be very little work done on this problem in layman terms. Also, this problem is NP-Complete so this solution will only be tractable with very low number. Your better off with a greedy approach i.e. sort by value/weight and then allocate. – CpILL Sep 14 at 6:42