0
7.0kviews
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.

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

1 Answer
2
636views

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 (W1), Row 2 means 2 items (W1, W2), Row 3 means 3 items (W1, W2, W3), Row 4 means 4 items (W1, W2, W3, W4).

Step 3 -

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

1


Step 4 -

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

2


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 W1 = 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 W1 = 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 W1 = 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 W1 = 2 kg and therefore, same item W1 can be placed in all the next knapsacks or the next columns in the [Row 1].

3


Computation for [Row 2] -

  • The [Row 2] carry 2 items that are W1 = 2 kg and W2 = 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 W1 = 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 W1 = 2 kg and W2 = 3 kg. That means we can put any of the item in [Col 3]. But, the profit corresponding to item W2 is more than profit corresponding to item W1 (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 W1 = 2 kg and W2 = 3 kg. But, the profit corresponding to item W2 is more than profit corresponding to item W1 (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 W1 = 2 kg and W2 = 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 W1 = 2 kg and W2 = 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 W1, W2, and therefore, same items can be placed in all the next knapsacks or the next columns in the [Row 2]

4


Computation for [Row 3] -

  • The [Row 3] carry 3 items that are W1 = 2 kg, W2 = 3 kg and W3 = 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 W1 = 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 W2 = 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 W3 = 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 W3 = 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 W3 = 4 kg and W1 = 2 kg together (4 kg + 2 kg = 6 kg). Because their correspoding profits together gave high profit that is (P3 + P1 = 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 W3 = 4 kg and W2 = 3 kg together (4 kg + 3 kg = 7 kg). Because their correspoding profits together gave high profit that is (P3 + P2 = 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 W3 = 4 kg and W2 = 3 kg together (4 kg + 3 kg = 7 kg). Because their correspoding profits together gave high profit that is (P3 + P2 = 5 + 2 = 7). Therefore, put profits corresponding to the weights 3 kg and 4 kg that is 2 + 5 = 7.

5


Computation for [Row 4] -

  • The [Row 4] carry 4 items that are W1 = 2 kg, W2 = 3 kg, W3 = 4 kg and W4 = 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 W1 = 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 W2 = 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 W3 = 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 W4 = 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 W3 = 4 kg and W1 = 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 W3 = 4 kg and W1 = 2 kg together (4 kg + 2 kg = 6 kg). Because their correspoding profits together gave high profit that is (P3 + P1 = 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 W4 = 5 kg and W1 = 2 kg together (5 kg + 2 kg = 7 kg). Because their correspoding profits together gave high profit that is (P4 + P1 = 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 W4 = 5 kg and W2 = 3 kg together (5 kg + 3 kg = 8 kg). Because their correspoding profits together gave high profit that is (P4 + P2 = 6 + 2 = 8). Therefore, put profits corresponding to the weights 3 kg and 5 kg that is 2 + 6 = 8.

6


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.

7

  • 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 (w2) and item 4 (w4).
Please log in to add an answer.