18

If there is more than one constraint (for example, both a volume limit and a weight limit, where the volume and weight of each item are not related), we get the multiply-constrained knapsack problem, multi-dimensional knapsack problem, or m-dimensional knapsack problem.

How do I code this in the most optimized fashion? Well, one can develop a brute force recursive solution. May be branch and bound.. but essentially its exponential most of the time until you do some sort of memoization or use dynamic programming which again takes a huge amount of memory if not done well.

The problem I am facing is this

I have my knapsack function KnapSack( Capacity, Value, i) instead of the common KnapSack ( Capacity , i ) since I have upper limits on both of those. can anyone guide me with this? or provide suitable resources for solving these problems for reasonably large n

or is this NP complete ?

Thanks

EFreak
  • 3,119
  • 3
  • 27
  • 31

5 Answers5

6

Merge the constraints. Look at http://www.diku.dk/~pisinger/95-1.pdf chapter 1.3.1 called Merging the Constraints.

An example is say you have
variable , constraint1 , constraint2
1 , 43 , 66
2 , 65 , 54
3 , 34 , 49
4 , 99 , 32
5 , 2 , 88

Multiply the first constraint by some big number then add it to the second constraint.

So you have
variable , merged constraint
1 , 430066
2 , 650054
3 , 340049
4 , 990032
5 , 20088

From there do whatever algorithm you wanted to do with one constraint. The main limiter that comes to mind with this how many digits your variable can hold.

user1934868
  • 99
  • 1
  • 5
  • 1
    Consider the following set of items: one single item with weighs [1,51] := 100051 your capacity is [2,50] := 200050. A normal one-dimensional knap-sack problem will think that the item fits as cleary 200050 > 100051 and will return the whole set of 1 item as the optimal selection. You need to modify the algorithm so that it decomposes the weight, and checks the components individually. EDIT: I realize now that my problem might only occur in optimization variants of the problem, not in "exact packings" – JMC Dec 17 '16 at 17:22
  • 1
    Theoretically the approach is very interesting. However, when solving the transformed problem with a solver, numerical issues will arise already for small instances. – Christian Jan 25 '19 at 15:50
4

As a good example would serve the following problem:

Given an undirected graph G having positive weights and N vertices.

You start with having a sum of M money. For passing through a vertex i, you must pay S[i] money. If you don't have enough money - you can't pass through that vertex. Find the shortest path from vertex 1 to vertex N, respecting the above conditions; or state that such path doesn't exist. If there exist more than one path having the same length, then output the cheapest one. Restrictions: 1

Pseudocode:

Set states(i,j) as unvisited for all (i,j)
Set Min[i][j] to Infinity for all (i,j)

Min[0][M]=0

While(TRUE)

Among all unvisited states(i,j) find the one for which Min[i][j]
is the smallest. Let this state found be (k,l).

If there wasn't found any state (k,l) for which Min[k][l] is
less than Infinity - exit While loop.

Mark state(k,l) as visited

For All Neighbors p of Vertex k.
   If (l-S[p]>=0 AND
    Min[p][l-S[p]]>Min[k][l]+Dist[k][p])
      Then Min[p][l-S[p]]=Min[k][l]+Dist[k][p]
   i.e.
If for state(i,j) there are enough money left for
going to vertex p (l-S[p] represents the money that
will remain after passing to vertex p), and the
shortest path found for state(p,l-S[p]) is bigger
than [the shortest path found for
state(k,l)] + [distance from vertex k to vertex p)],
then set the shortest path for state(i,j) to be equal
to this sum.
End For

End While

Find the smallest number among Min[N-1][j] (for all j, 0<=j<=M);
if there are more than one such states, then take the one with greater
j. If there are no states(N-1,j) with value less than Infinity - then
such a path doesn't exist.
EFreak
  • 3,119
  • 3
  • 27
  • 31
  • 3
    Is your answer related to the question? I don't get it. If not related then did you end up using the cube style dynamic algo or something else? – basarat Mar 13 '15 at 13:04
2

Knapsack with multiple constraints is a packing problem. Read up. http://en.wikipedia.org/wiki/Packing_problem

Pranav
  • 3,340
  • 8
  • 35
  • 48
  • 3
    this is a general read ..didn help me much.. since most of the discussed cases are geometric problems and explanations are too small – EFreak Dec 01 '09 at 19:04
0

There are greedy like heuristics that calculate an "efficiency" for each item, that run quickly and yield approximate solutions.

You can use a branch and bound algorithm. You can get an initial lower bound using a greedy like heuristic, which can be used to initialize the incumbent solution. You can calculate upper bounds for various sub-problems by considering each of the m constraints one at time (relaxing the other constraints in the problem), then use the lowest of these bounds as an upper bound for the original problem. This technique is due to Shih. However this technique probably won't work well if no particular constraint tends to dominate the solution, or if the initial solution from the greedy like heuristic is not close to the optimum.

There are better more modern algorithms which are harder to implement, see "multidimensional knapsack problem" papers by J Puchinger!

gornvix
  • 3,154
  • 6
  • 35
  • 74
-3

As you said vol and weight both are positive quantities, try to use that fact that weight always decreases:

knap[position][vol][t]

Now t=0 when wt is positive, t=1 when wt is negative.

Paul Roub
  • 36,322
  • 27
  • 84
  • 93
Teja Vardhan Reddy
  • 1