0/1 knapsack problem

In 0/1 Knapsack Problem,

• As the name suggests, items are indivisible here.
• 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 dynamic programming approach.

​

Amity School of Engineering & Technology

Find the optimal solution for the 0/1 knapsack problem making use of dynamic programming approach. Consider-

n = 4

C= 8kg

P= (1,2,5,6)

W= (2,3, 4, 5)

​

Amity School of Engineering & Technology

0/1 Knapsack Problem Using Dynamic Programming-�

Step-01:

​

• Draw a table say ‘T’ with (n+1) number of rows and (C+1) number of columns.
• Fill all the boxes of 0^th row and 0^th column with zeroes as shown-

​

Amity School of Engineering & Technology

Amity School of Engineering & Technology

Step-02:

• Start filling the table row wise top to bottom from left to right.
• Use the following formula-

​

T (i , j) = max { T ( i-1 , j ) , value_i + T( i-1 , j – weight_i ) }

Here, T(i , j) = maximum value of the selected items if we can take items 1 to i and have weight restrictions of j.

Amity School of Engineering & Technology

Step-03:

To identify the items that must be put into the knapsack to obtain that maximum profit,

• Consider the last column of the table.
• Start scanning the entries from bottom to top.
• On encountering an entry whose value is not same as the value stored in the entry immediately above it, mark the row label of that entry.
• After all the entries are scanned, the marked labels represent the items that must be put into the knapsack.

​

Amity School of Engineering & Technology

Problem-2

Find the optimal solution for the 0/1 knapsack problem making use of dynamic programming approach. Consider-

n = 4

C= 5 kg

(w1, w2, w3, w4) = (2, 3, 4, 5)

(b1, b2, b3, b4) = (3, 4, 5, 6)

​

Amity School of Engineering & Technology

Amity School of Engineering & Technology

Amity School of Engineering & Technology

Problem-3

Find the optimal solution for the 0/1 knapsack problem making use of dynamic programming approach. Consider-

n = 5

C= 11 kg

(w1, w2, w3, w4,w5) = (1,2,5,6,7)

(p1,p2,p3,p4,p5) = (1,6,18,22,28)

​

Amity School of Engineering & Technology

Answer

• Max profit-40
• (0,0,1,1,0)

​

Amity School of Engineering & Technology