HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Multi- Knapsack problem variation

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
knapsackmultiproblemvariation

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#81186, answer score: 2

Revisions (0)

No revisions yet.