0
14kviews
Define Knapsack problem. Solve the following 0/1 Knapsack problem using dynamic programming Let n=3 , p={1,2,5), w=(2,3,4) and m=6

Define Knapsack problem. Solve the following 0/1 Knapsack problem using dynamic programming Let n=3 , p={1,2,5), w=(2,3,4) and m=6

1 Answer
2
1.6kviews

Knapsack Problem

  • knapsack is like a container or a bag with limited weight capacity and a few items each having some weight and value.

  • If we have given some items which have some weights or profits then we have to put some items in the knapsack in such a way that total value produces a maximum profit.

  • The Knapsack Problem states which items should be placed into the knapsack such that,

    • The value of profit obtained by putting the items into the knapsack is maximum.
    • And the weight limit of the knapsack does not exceed.
  • There are two types of knapsack problems as follows:

    • Fractional Knapsack Problem
    • 0/1 Knapsack Problem
  • Here, we see a 0/1 Knapsack Problem.

0/1 Knapsack Problem

  • In 0/1 Knapsack Problem as the name suggests, items are indivisible here.
  • That means we can not take the fraction of any item.
  • We have to either take an item completely or leave it completely.
  • It is solved using a dynamic programming approach.

Let's solve the given 0/1 knapsack problem using a dynamic programming approach.

The given data -

n = 3

p = Profit = {1, 2, 5) = {p1, p2, p3}

w = Weight = (2, 3, 4) = {w1, w2, w3}

m = 6


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] = [3 + 1, 6 + 1] = [4, 7]$ 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 6 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).

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.

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.

5


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 = 6.

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.

6

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