written 2.5 years ago by
binitamayekar
★ 6.5k
|
•
modified 2.5 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 (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.
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.
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].
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]
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.
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.
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 (w2) and item 4 (w4).