When there's 1 property, I do understand what's going on in there. I'm having a problem with understanding knapsack problem when there's more than 1 property.
I have to write a program that uses knapsack algorithm with a 2 properties. Teacher told us, It has to be done in a 3d array. I can't imagine how would such array look like.
Let's say here's my input:
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 output would look like that:
4 // the cheapest sum of costs of 2 records
1 3 // numbers of these 2 records
The explanation of output: 2 sets of records fit's into 1'st 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
Because 1st set of the records is the cheapest (4 < 5), we chose it. Not only I'll have to find out whether such set of records exists, I'll also have to find records I've summed.
But for now, I only need to understand, how will 3d array look like. Could some of You help me out with that and show, layer by layer, just like in my image, how would this look like? Thanks.
Greedy algorithm. A greedy algorithm is the most straightforward approach to solving the knapsack problem, in that it is a one-pass algorithm that constructs a single final solution.
Nested knapsack problem. Collapsing knapsack problem. Nonlinear knapsack problem. Inverse-parametric knapsack problem.
The 0/1 knapsack problem means that the items are either completely or no items are filled in a knapsack. For example, we have two items having weights 2kg and 3kg, respectively. If we pick the 2kg item then we cannot pick 1kg item from the 2kg item (item is not divisible); we have to pick the 2kg item completely.
Say you are using a three dimension table: A[x][y][z]=k
, x
: sum 1st property; y
: sum 2nd property; z
: sum 3rd property; k: minimal cost (maximal reward, which I prefer using reward)
So you iterate over items. Say current item is (p1, p2, p3, reward) (reward = - cost). for each (x,y,z,k)
, your update formula:
A[x+p1][y+p2][z+p3] = max(A[x+p1][y+p2][z+p3], A[x+p1][y+p2][z+p3] + reward)
If the 1st term on RHS is greater, on slot A[x+p1][y+p2][z+p3]
, the configuration of knapsack is remain still; otherwise, you update the knapsack by that of A[x+p1][y+p2][z+p3]
plus the current item.
Hope this cut things clear.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With