How can I solve knapsack problems with 3 variables?

Question

What's the best way to solve problems related to knapsack problems, which have 3 variables, such as: value, weight and volume? (with the biggest value possible, with a maximum weight and volume limit)

I have tried using a defined index, based on its value/(weight*volume) but I believe that this won't give me the best solution, so I searched and some people suggest using dynamic programming, but all topics related to that, only have 2 variables (value and weight) and I don't know how having more than 2 variables can affect this.

Answer 1

You should be able to extend the standard dynamic programming problem with one constraint to handle two or more constraints.

As a refresher, the standard DP solution for the knapsack problem works by ordering the items in some order, then answering all questions of the following form:

What is the maximum value that can be produced using the first i items without exceeding weight w?

This turns into a 2D table, with one axis for how many items are being considered and another for the different possible weight values. To fill in the table, you fill in the 1D slice of entries where i = 0 by setting them to zero (you can’t get any value if you have no items), then filling in the 1D slice where i = 1 by considering whether to include or exclude the first item, the slice where i = 2 by considering whether to include or exclude the second item, etc. The runtime is then O(nW), where n is the number of items and W is the maximum allowable weight, since those are the dimensions of the table and you do O(1) work per entry.

If you now have two constraints (weight and volume), you can solve all problems of the following form:

What is the maximum value that can be produced using the first i items without exceeding weight w or volume v?

This turns into a 3D table, with one axis for how many items are being considered, another for the different possible weight values, and a third for the possible volume values. To fill in the table, you fill in the 2D slice of entries where i = 0 by setting them to zero (you can’t get any value if you have no items), then filling in the 2D slice where i = 1 by considering whether to include or exclude the first item, the slice where i = 2 by considering whether to include or exclude the second item, etc. The runtime is O(nWV), where n is the number of items, W is the maximum allowable weight, and V is the maximum allowable volume(instead of value), since that’s the number of table entries and it takes O(1) work to fill each in.

Do you see how to adapt this for larger numbers of constraints?

Answer 2

Let's say that you have value, weight, and volume as your parameters and you want to compute the maximum value that you can have without exceeding the weight and volume limit initially available, using dynamic programming. Dynamic programming is based on a recursive formula. Therefore, here I will only tell you the recursive formula and it won't be hard to do the implementation.

I use V to refer to the initial volume available, and W to the initial weight available. Also, I use volume[] to refer to the array that is holding volumes, similarly weight[] the array for weights.

So, the 3 parameters you need for the dynamic programming algorithm are (1) Which item you're currently examining (call it i), (2) how much volume do you have left (call it vLeft), and (3) how much weight do you have left (call it wLeft).

And to optimize that you can use the following recursion:

DP[i][vLeft][wLeft] = min(DP[i + 1][vLeft - volume[i]][wLeft - weight[i]], DP[i + 1][vLeft][wLeft])

The left argument in the min function is when we pick the item and the right one is when we don't. Also, you need some base conditions for when there is no volume or weight left, and when i reach the last item.

But your initial call would be something like this, where 0 is the starting index.

ComputeAnswer(0, V, W)