Knapsack algorithm with two properties. How to implement this in a 3d array?

Question

I have a problem understanding an issue with a backpack when there are more than 1 properties. When there is 1 property,

I need to write a program that uses a knapsack algorithm with two properties. Teacher told us that this needs to be done in a 3d array. An incorrect implementation will result in O (2 ^ n) processing time. I can’t imagine what such an array looks like.

Let's say my input here:

4 3 4 // number of records below, 1st property of backpack, 2nd property of backpack 1 1 1 // 1st property, 2nd property, cost 1 2 2 // 1st property, 2nd property, cost 2 3 3 // 1st property, 2nd property, cost 3 4 5 // 1st property, 2nd property, cost 

And the result will look like this:

 4 // the cheapest sum of costs of 2 records 1 3 // numbers of these 2 records 

Explanation of the output: 2 sets of records fit into the 1st line of input:

(1) - record number 1 and record number 3

  1 1 1 + 2 3 3 ------- 3 4 4 

(2) - record number 4

  3 4 5 

Since the first set of records is the cheapest (4 <5), we chose it. Not only do I need to find out if such a set of records exists, I also have to find the records that I have summarized.

But for now, I only need to understand what a 3D array will look like. Can any of you help me with this and show, in layers, as in my image, how it will look? Thanks.

Answer 1

Converting from a problem solving algorithm with a 1-restrictive backpack with dynamic programming to solve a problem with two constraints is very simple. For someone to draw a three-dimensional image that shows you what is happening there, I think it is difficult. The algorithm, on the other hand, is pretty simple:

I assume that you need an exact solution, and you want to minimize the cost, rather than maximize the value (which I got from your example). Earlier, I did not do any of these options, so I can not guarantee that there was no error.

1-restriction

The matrix for the task with a 1-restrictive backpack (item x weight) stores the value in each position.

The algorithm is basically:

 // WL = backpack weight limit A[0, 0] = 0 for w = 1, 2, ..., WL // weight A[0, w] = INFINITY for i = 1, 2, ..., n // items for w = 0, 1, ..., WL // weight // wi and ci are the weight and cost of the item respectively // A[i-1, w-wi] + ci = 0 when wi > w A[i, w] = min(A[i-1, w], A[i-1, w-wi] + ci) 

2-restriction

Now, to extend this to include, add another restriction: (let's say size is another restriction)

The matrix will be (item x weight x size) .

 // WL = backpack weight limit // SL = backpack size limit for w = 0, 1, ..., WL // weight for s = 0, 1, ..., SL // size A[0, w, s] = INFINITY A[0, 0, 0] = 0 for i = 1, 2, ..., n // items for w = 0, 1, ..., WL // weight for s = 0, 1, ..., SL // size // wi, si and ci are the weight, size and cost of the item respectively // A[i-1, w-wi, s-si] + ci = 0 when wi > w or si > s A[i, w, s] = min(A[i-1, w, s], A[i-1, w-wi, s-si] + ci) 

Answer 2

You are trying to do something impossible - this is your problem.

When you add a number of dimensions, your objects get additional properties. Thus, instead of the left side of the table column ( prop1 ), you have the side of the rectangle ( prop1 x prop2 ) or the side of the block (prop1 x prop2 x prop3 ) and so on. But existing constraints that define the top of a row in a table must have the same number of dimensions. Not just one dimension! . That way, you can never put a problem with two properties into a three-dimensional block, instead you need a 4D block. 6D block for 3 properties and so on.