algorithm - Multiple Constraint Knapsack Problem

Question

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

Answer 1

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.