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

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 (W₁), Row 2 means 2 items (W₁, W₂), Row 3 means 3 items (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.

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.

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.

• 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 (w₁) and item 3 (w₃).