For a 0-1 knapsack problem with given weights and values of n items, and a maximum weight capacity W, I know it can be solved with a double nested loop using dynamic approach.
My question is if we say that each of the n items have an additional "volume" value and a maximum volume capacity V, then how do I change the algorithm? Will the algorithm becomes a triple nested loop with time complexity O(n*W*V)?
0-1 knapsack dynamic programming with two constraints
Viewed 255
1 Answers
If there is a weight and volume constraint then this is an instance of the multi-dimensional 0-1 knapsack problem. The two dimensional knapsack problem is computationally harder than the one dimensional case so the algorithm you use for the 1D case simply no longer works. For 2D and above the 0-1 knapsack problem is NP-complete.
Related