Let n=4 Profit={1, 2, 5, 6} Weight= {2, 3, 4, 5} M=8 Find solution to 0/1 Knapsack Problem using Dynamic Programming.

865views

written 2.7 years ago by

binitamayekar ★ 6.6k

• modified 2.7 years ago

0/1 Knapsack Problem using Dynamic Programming

The given data -

n = 4

Profit = {1, 2, 5, 6} = {p1, p2, p3, p4}

Weight = {2, 3, 4, 5} = {w1, w2, w3, w4}

M = 8

Step 1 -

Arrange the weights in the ascending order along with their corresponding profits.
But, in the given question weights are already in ascending order, therefore, no need to do this here.

Step 2 -

Generate matrix table of size (n + 1) rows and (M + 1) columns.
Therefore, here $[n + 1, M + 1] = [4 + 1, 8 + 1] = [5, 9]$ marix table is used to solve the problem.
In that, columns represent the knapsack capacity in weights like 0 kg, 1 kg, 2 kg upto 8 kg and rows represent the number of items it holds like Row 0 means no item, Row 1 means 1 item (W₁), Row 2 means 2 items (W₁, W₂), Row 3 means 3 items (W₁, W₂, W₃), Row 4 means 4 items (W₁, W₂, W₃, W₄).

Step 3 -

The first row [Row 0] and the first column [Col 0] would be 0 as there is no item given whose weight W_i = 0.

Step 4 -

The second column [Col 1] that represent 1 kg weight also would be 0 because there is no item given whose weight W_i = 1 kg.
The minimum weight item given in the question is 2 kg.

Step 5 -

Now, fill the matrix table row-wise.

Computation for [Row 1] -

Starts with second row [Row 1] which carry only 1 items that is W₁ = 2 kg.
Now, check it against each column or knapsack capacity.
[Row 1][Col 1] is already filled with 0 because no item given can fulfill the knapsack of capacity 1 kg.
[Row 1][Col 2] in this capacity of the knapsack is 2 kg and we have the only 1 item is also of W₁ = 2 kg, therefore, we can fill the knapsack with this item of weight equal to 2 kg. Hence, put profit corresponding to the weight of 2 kg that is 1.
[Row 1][Col 3] in this capacity of the knapsack is 3 kg and we have the only 1 item of W₁ = 2 kg therefore, we can fill the knapsack with this item of weight equal to 2 kg. Hence, put profit corresponding to the weight of 2 kg that is 1.
Similarly for next all columns of the [Row 1] we put profit corresponding to the weight of 2 kg which is 1. Because the [Row 1] holds only 1 items of W₁ = 2 kg and therefore, same item W₁ can be placed in all the next knapsacks or the next columns in the [Row 1].

Computation for [Row 2] -

The [Row 2] carry 2 items that are W₁ = 2 kg and W₂ = 3 kg.
Now, check it against each column or knapsack capacity.
[Row 1][Col 1] is already filled with 0 because no item given can fulfill the knapsack of capacity 1 kg.
[Row 2][Col 2] in this capacity of the knapsack is 2 kg and we have 1 item of W₁ = 2 kg therefore, we can fill the knapsack with this item of weight equal to 2 kg. Hence, put profit corresponding to the weight of 2 kg that is 1.
[Row 2][Col 3] in this capacity of the knapsack is 3 kg and we have 2 items that are W₁ = 2 kg and W₂ = 3 kg. That means we can put any of the item in [Col 3]. But, the profit corresponding to item W₂ is more than profit corresponding to item W₁ (p2 > p1 i.e. 2 > 1). Hence, we can fill the knapsack with the item of weight equal to 3 kg. Therefore, put profit corresponding to the weight 3 kg that is 2.
[Row 2][Col 4] in this capacity of the knapsack is 4 kg and we have 2 items that are W₁ = 2 kg and W₂ = 3 kg. But, the profit corresponding to item W₂ is more than profit corresponding to item W₁ (p2 > p1 i.e. 2 > 1). Hence, we can fill the knapsack with the item of weight equal to 3 kg. Therefore, put profit corresponding to the weight 3 kg that is 2.
[Row 2][Col 5] in this capacity of the knapsack is 5 kg and we have 2 items that are W₁ = 2 kg and W₂ = 3 kg. Here, we can put both items together in the knapsack (3 kg + 3 kg = 5kg) because here knapsack capacity is 5 kg. Therefore, put profits corresponding to the weights 2 kg and 3kg that is 1 + 2 = 3.
[Row 2][Col 6] in this capacity of the knapsack is 6 kg and we have 2 items that are W₁ = 2 kg and W₂ = 3 kg. Here also we can put both items together in the knapsack. Therefore, put profits corresponding to the weights 2 kg and 3 kg that is 1 + 2 = 3.
Similarly for next all columns of the [Row 2] we put profit corresponding to the weights 2 kg and 3 kg which is 1 + 2 = 3. Because the [Row 2] holds only 2 items of W₁, W₂, and therefore, same items can be placed in all the next knapsacks or the next columns in the [Row 2]

Computation for [Row 3] -

The [Row 3] carry 3 items that are W₁ = 2 kg, W₂ = 3 kg and W₃ = 4 kg.
Now, check it against each column or knapsack capacity.
[Row 3][Col 1] is already filled with 0 because no item given can fulfill the knapsack of capacity 1 kg.
[Row 3][Col 2] in this capacity of the knapsack is 2 kg and we have 1 item of W₁ = 2 kg therefore, we can fill the knapsack with this item of weight equal to 2 kg. Hence, put profit corresponding to the weight 2 kg that is 1.
[Row 3][Col 3] in this capacity of the knapsack is 3 kg and we have 1 item W₂ = 3 kg therefore, we can fill the knapsack with this item of weight equal to 3 kg. Hence, put profit corresponding to the weight of 3 kg that is 2.
[Row 3][Col 4] in this capacity of the knapsack is 4 kg and we have 1 item W₃ = 4 kg therefore, we can fill the knapsack with this item of weight equal to 4 kg. Hence, put profit corresponding to the weight of 4 kg that is 5.
[Row 3][Col 5] in this capacity of the knapsack is 5 kg and we have 3 items out of that item W₃ = 4 kg has the high profit, therefore, we can fill the knapsack with this item of weight equal to 4 kg. Hence, put profit corresponding to the weight of 4 kg that is 5.
[Row 3][Col 6] in this capacity of the knapsack is 6 kg and we have 3 items out of that we put items W₃ = 4 kg and W₁ = 2 kg together (4 kg + 2 kg = 6 kg). Because their correspoding profits together gave high profit that is (P₃ + P₁ = 5 + 1 = 6). Therefore, put profits corresponding to the weights 2 kg and 4 kg that is 1 + 5 = 6.
[Row 3][Col 7] in this capacity of the knapsack is 7 kg and we have 3 items out of that we put items W₃ = 4 kg and W₂ = 3 kg together (4 kg + 3 kg = 7 kg). Because their correspoding profits together gave high profit that is (P₃ + P₂ = 5 + 2 = 7). Therefore, put profits corresponding to the weights 3 kg and 4 kg that is 2 + 5 = 7.
[Row 3][Col 8] in this capacity of the knapsack is 7 kg and we have 3 items out of that we put items W₃ = 4 kg and W₂ = 3 kg together (4 kg + 3 kg = 7 kg). Because their correspoding profits together gave high profit that is (P₃ + P₂ = 5 + 2 = 7). Therefore, put profits corresponding to the weights 3 kg and 4 kg that is 2 + 5 = 7.

Computation for [Row 4] -

The [Row 4] carry 4 items that are W₁ = 2 kg, W₂ = 3 kg, W₃ = 4 kg and W₄ = 5 kg.
Now, check it against each column or knapsack capacity.
[Row 4][Col 1] is already filled with 0 because no item given can fulfill the knapsack of capacity 1 kg.
[Row 4][Col 2] in this capacity of the knapsack is 2 kg and we have 1 item of W₁ = 2 kg therefore, we can fill the knapsack with this item of weight equal to 2 kg. Hence, put profit corresponding to the weight of 2 kg that is 1.
[Row 4][Col 3] in this capacity of the knapsack is 3 kg and we have 1 item W₂ = 3 kg therefore, we can fill the knapsack with this item of weight equal to 3 kg. Hence, put profit corresponding to the weight of 3 kg that is 2.
[Row 4][Col 4] in this capacity of the knapsack is 4 kg and we have 1 item W₃ = 4 kg therefore, we can fill the knapsack with this item of weight equal to 4 kg. Hence, put profit corresponding to the weight of 4 kg that is 5.
[Row 4][Col 5] in this capacity of the knapsack is 5 kg and we have 1 item W₄ = 5 kg therefore, we can fill the knapsack with this item of weight equal to 5 kg. Hence, put profit corresponding to the weight 5 kg that is 6. (In this items W₃ = 4 kg and W₁ = 2 kg also can put together (4 kg + 2 kg = 6 kg) because they also gave same profit 6)
[Row 4][Col 6] in this capacity of the knapsack is 6 kg and we have 4 items out of that we put items W₃ = 4 kg and W₁ = 2 kg together (4 kg + 2 kg = 6 kg). Because their correspoding profits together gave high profit that is (P₃ + P₁ = 5 + 1 = 6). Therefore, put profits corresponding to the weights 2 kg and 4 kg that is 1 + 5 = 6.
[Row 4][Col 7] in this capacity of the knapsack is 7 kg and we have 4 items out of that we put items W₄ = 5 kg and W₁ = 2 kg together (5 kg + 2 kg = 7 kg). Because their correspoding profits together gave high profit that is (P₄ + P₁ = 6 + 1 = 7). Therefore, put profits corresponding to the weights 2 kg and 5 kg that is 1 + 6 = 7.
[Row 3][Col 8] in this capacity of the knapsack is 8 kg and we have 4 items out of that we put items W₄ = 5 kg and W₂ = 3 kg together (5 kg + 3 kg = 8 kg). Because their correspoding profits together gave high profit that is (P₄ + P₂ = 6 + 2 = 8). Therefore, put profits corresponding to the weights 3 kg and 5 kg that is 2 + 6 = 8.

Step 6 -

The last entry in the matrix table represents the maximum possible profit that can be gained by the knapsack.
So, the maximum possible profit that can be gained by the knapsack = 8.

Step 7 -

Now, identify the items that must be put into the knapsack to obtain that maximum profit.
Consider the last cell of the table.
Start scanning the entries from bottom to top.
On encountering an entry whose value is not the same as the value stored in the entry immediately above it, mark the row label of that entry.
Then, subtract the corresponding row profit from the entry to get a new entry for the next scan.
After all the entries are scanned, the marked labels represent the items that must be put into the knapsack.

Therefore,
In the given matrix table start from the last cell [Row 4][Col 8] = 8.
Start scanning the table for entry 8 from bottom to top.
But, we dont find any entry for 8, therefore, marked the [Row 4].
Then, subtract [Row 4] profit that is 6 from entry 8. Therefore, 8 - 6 = 2.
Now, scan for entry 2 from bottom to top.
Entry for 2 was found in [Row 4], [Row 3], [Row 2] but, not found in [Row 1] and therefore marked the [Row 2].
Then, subtract [Row 2] profit that is 2 from entry 2. Therefore, 2 - 2 = 0.
Stop the process.
Finally, we get marked rows [Row 2] and [Row 4] thus, items that must be put into the knapsack to obtain the maximum profit 8 are item 2 (w₂) and item 4 (w₄).

ADD COMMENT EDIT