written 2.2 years ago by
binitamayekar
★ 6.5k

•
modified 2.2 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_{1}), Row 2 means 2 items (W_{1}, W_{2}), Row 3 means 3 items (W_{1}, W_{2}, W_{3}), Row 4 means 4 items (W_{1}, W_{2}, W_{3}, W_{4}).
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 rowwise.
Computation for [Row 1] 
 Starts with second row [Row 1] which carry only 1 items that is W_{1} = 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_{1} = 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_{1} = 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_{1} = 2 kg and therefore, same item W_{1} 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_{1} = 2 kg and W_{2} = 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_{1} = 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_{1} = 2 kg and W_{2} = 3 kg. That means we can put any of the item in [Col 3]. But, the profit corresponding to item W_{2} is more than profit corresponding to item W_{1} (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_{1} = 2 kg and W_{2} = 3 kg. But, the profit corresponding to item W_{2} is more than profit corresponding to item W_{1} (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_{1} = 2 kg and W_{2} = 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_{1} = 2 kg and W_{2} = 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_{1}, W_{2}, 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_{1} = 2 kg, W_{2} = 3 kg and W_{3} = 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_{1} = 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_{2} = 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_{3} = 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_{3} = 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_{3} = 4 kg and W_{1} = 2 kg together (4 kg + 2 kg = 6 kg). Because their correspoding profits together gave high profit that is (P_{3} + P_{1} = 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_{3} = 4 kg and W_{2} = 3 kg together (4 kg + 3 kg = 7 kg). Because their correspoding profits together gave high profit that is (P_{3} + P_{2} = 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_{3} = 4 kg and W_{2} = 3 kg together (4 kg + 3 kg = 7 kg). Because their correspoding profits together gave high profit that is (P_{3} + P_{2} = 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_{1} = 2 kg, W_{2} = 3 kg, W_{3} = 4 kg and W_{4} = 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_{1} = 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_{2} = 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_{3} = 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_{4} = 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_{3} = 4 kg and W_{1} = 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_{3} = 4 kg and W_{1} = 2 kg together (4 kg + 2 kg = 6 kg). Because their correspoding profits together gave high profit that is (P_{3} + P_{1} = 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_{4} = 5 kg and W_{1} = 2 kg together (5 kg + 2 kg = 7 kg). Because their correspoding profits together gave high profit that is (P_{4} + P_{1} = 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_{4} = 5 kg and W_{2} = 3 kg together (5 kg + 3 kg = 8 kg). Because their correspoding profits together gave high profit that is (P_{4} + P_{2} = 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_{2}) and item 4 (w_{4}).