Tag: 0 1 knapsack problem dynamic programming algorithm example

0/1 Knapsack Problem using Dynamic Programming Approach

Knapsack Problem-

 

You are given a knapsack (a kind of shoulder bag) with a limited weight capacity and few items each having some weight and value.

The problem states-

“Which items should be placed in the knapsack so that the value or profit that is obtained by putting the items in the knapsack is maximum and the weight limit of the knapsack also does not exceed?”

 

 

Knapsack Problem Variants-

 

Knapsack problem has the following two variants-

  1. Fractional Knapsack Problem
  2. 0/1 Knapsack Problem

 

In this article, we will discuss about 0/1 Knapsack Problem.

 

Also read- Fractional Knapsack Problem

 

0/1 Knapsack Problem-

 

In 0/1 Knapsack Problem,

  • As the name suggests, items are indivisible i.e. 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.

 

Steps for solving 0/1 Knapsack Problem using Dynamic Programming Approach-

 

Consider we are given-

  • A knapsack of weight capacity ‘w’
  • ‘n’ number of items each having some weight and value

 

Step-01:

 

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

 

 

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 ) , valuei + T( i-1 , j – weight) }

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

 

Step-03:

 

After filling the table completely, value of the last box represents the maximum possible value that be put in the knapsack.

 

Step-04:

 

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

  • Considering the last column of the table, start scanning the entries from bottom to top.
  • If an entry is encountered whose value is not same as the value which is stored in the entry immediately above it, then mark the row label of that entry.
  • After scanning all the entries, the marked labels represent the items that must be put in the knapsack.

 

Time Complexity-

 

  • It takes θ(nw) time to fill (n+1)(w+1) table entries where each entry takes constant time θ(1) for its computation.
  • It takes θ(n) time for tracing the solution as the tracing process traces the n rows starting from row n and then moving up by 1 row at every step.
  • Thus, overall θ(nw) time is taken to solve 0/1 knapsack problem using dynamic programming approach.

 

PRACTICE PROBLEM BASED ON 0/1 KNAPSACK PROBLEM USING DYNAMIC PROGRAMMING APPROACH-

 

Problem-

 

For the given set of items and knapsack capacity = 5 kg, find the optimal solution for the 0/1 knapsack problem making use of dynamic programming approach.

 

ItemWeightValue
123
234
345
456

 

OR

 

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

n = 4

w = 5 kg

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

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

 

OR

 

A thief enters a house for robbing it. He can carry a maximal weight of 5 kg into his bag. There are 4 items in the house with the following weights and values. What items should thief take if he either takes the item completely or leaves it completely?

 

ItemWeight (kg)Value ($)
Mirror23
Silver nugget34
Painting45
Vase56

 

Solution-

 

Given-

 

  • Knapsack capacity (w) = 5 kg
  • Number of items (n) = 4

 

Step-01:

 

  • Draw a table say ‘T’ with (n+1) = 4 + 1 = 5 number of rows and (w+1) = 5 + 1 = 6 number of columns.
  • Fill all the boxes of 0th row and 0th column with 0.

 

 

Step-02:

 

Start filling the table row wise top to bottom from left to right using the formula-

T (i , j) = max { T ( i-1 , j ) , valuei + T( i-1 , j – weight) }

 

Finding T(1,1)-

 

We have,

i = 1

j = 1

(value)i = (value)1 = 3

(weight)i = (weight)1 = 2

 

Substituting the values, we get-

T(1,1) = max { T(1-1 , 1) , 3 + T(1-1 , 1-2) }

T(1,1) = max { T(0,1) , 3 + T(0,-1) }

T(1,1) = T(0,1)             { Ignore T(0,-1) }

T(1,1) = 0

 

Finding T(1,2)-

 

We have,

i = 1

j = 2

(value)i = (value)1 = 3

(weight)i = (weight)1 = 2

 

Substituting the values, we get-

T(1,2) = max { T(1-1 , 2) , 3 + T(1-1 , 2-2) }

T(1,2) = max { T(0,2) , 3 + T(0,0) }

T(1,2) = max {0 , 3+0}

T(1,2) = 3

 

Finding T(1,3)-

 

We have,

i = 1

j = 3

(value)i = (value)1 = 3

(weight)i = (weight)1 = 2

 

Substituting the values, we get-

T(1,3) = max { T(1-1 , 3) , 3 + T(1-1 , 3-2) }

T(1,3) = max { T(0,3) , 3 + T(0,1) }

T(1,3) = max {0 , 3+0}

T(1,3) = 3

 

Finding T(1,4)-

 

We have,

i = 1

j = 4

(value)i = (value)1 = 3

(weight)i = (weight)1 = 2

 

Substituting the values, we get-

T(1,4) = max { T(1-1 , 4) , 3 + T(1-1 , 4-2) }

T(1,4) = max { T(0,4) , 3 + T(0,2) }

T(1,4) = max {0 , 3+0}

T(1,4) = 3

 

Finding T(1,5)-

 

We have,

i = 1

j = 5

(value)i = (value)1 = 3

(weight)i = (weight)1 = 2

 

Substituting the values, we get-

T(1,5) = max { T(1-1 , 5) , 3 + T(1-1 , 5-2) }

T(1,5) = max { T(0,5) , 3 + T(0,3) }

T(1,5) = max {0 , 3+0}

T(1,5) = 3

 

Finding T(2,1)-

 

We have,

i = 2

j = 1

(value)i = (value)2 = 4

(weight)i = (weight)2 = 3

 

Substituting the values, we get-

T(2,1) = max { T(2-1 , 1) , 4 + T(2-1 , 1-3) }

T(2,1) = max { T(1,1) , 4 + T(1,-2) }

T(2,1) = T(1,1)           { Ignore T(1,-2) }

T(2,1) = 0

 

Finding T(2,2)-

 

We have,

i = 2

j = 2

(value)i = (value)2 = 4

(weight)i = (weight)2 = 3

 

Substituting the values, we get-

T(2,2) = max { T(2-1 , 2) , 4 + T(2-1 , 2-3) }

T(2,2) = max { T(1,2) , 4 + T(1,-1) }

T(2,2) = T(1,2)           { Ignore T(1,-1) }

T(2,2) = 3

 

Finding T(2,3)-

 

We have,

i = 2

j = 3

(value)i = (value)2 = 4

(weight)i = (weight)2 = 3

 

Substituting the values, we get-

T(2,3) = max { T(2-1 , 3) , 4 + T(2-1 , 3-3) }

T(2,3) = max { T(1,3) , 4 + T(1,0) }

T(2,3) = max { 3 , 4+0 }

T(2,3) = 4

 

Finding T(2,4)-

 

We have,

i = 2

j = 4

(value)i = (value)2 = 4

(weight)i = (weight)2 = 3

 

Substituting the values, we get-

T(2,4) = max { T(2-1 , 4) , 4 + T(2-1 , 4-3) }

T(2,4) = max { T(1,4) , 4 + T(1,1) }

T(2,4) = max { 3 , 4+0 }

T(2,4) = 4

 

Finding T(2,5)-

 

We have,

i = 2

j = 5

(value)i = (value)2 = 4

(weight)i = (weight)2 = 3

 

Substituting the values, we get-

T(2,5) = max { T(2-1 , 5) , 4 + T(2-1 , 5-3) }

T(2,5) = max { T(1,5) , 4 + T(1,2) }

T(2,5) = max { 3 , 4+3 }

T(2,5) = 7

 

Similarly, after computing all the values and filling them in the table, we get-

 

 

  • The last entry represents the maximum possible value that can be put in the knapsack.
  • Thus, maximum possible value that can be put in the knapsack = 7

 

Identifying the items that must be put in the knapsack-

 

  • Considering the last column, start scanning the entries from bottom to top.
  • If an entry is encountered whose value is not same as the value which is stored in the entry immediately above it, then mark the label of row of that entry.

 

Following this,

  • We mark the rows labelled “1” and “2”.
  • Thus, items that must be put in the knapsack to obtain the maximum value 7 are-

Item-1 and Item-2

 

To gain better understanding about 0/1 Knapsack Problem,

Watch this Video lecture

 

Download the handwritten notes of “0/1 Knapsack Problem Using Dynamic Approach” here-

Get more notes and other study material of Design and Analysis of Algorithms (DAA).

Watch video lectures by visiting our YouTube channel LearnVidFun.