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

Knapsack with multiple constraints is a packing problem. Read up. http://en.wikipedia.org/wiki/Packing%5Fproblem

Answer 2

Have you checked out this Wikipedia page yet?

Answer 3

Take a look at my entry here: Python; or here: Python, generalized DP

• Tell me if it was of use. - Paddy.