0/1 Knapsack Using Dynamic Programming Approach with Source Code

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

Definition

The most common problem being solved is the 0-1 knapsack problem, which restricts the number  of copies of each kind of item to zero or one. Given a set of  items numbered from 1 up to , each with a weight  and a value , along with a maximum weight capacity ,

Maximize  

subject to  and .

Here  represents the number of instances of item  to include in the knapsack. Informally, the problem is to maximize the sum of the values of the items in the knapsack so that the sum of the weights is less than or equal to the knapsack's capacity.

The bounded knapsack problem (BKP) removes the restriction that there is only one of each item, but restricts the number  of copies of each kind of item to a maximum non-negative integer value :

maximize 

subject to  and 

The unbounded knapsack problem (UKP) places no upper bound on the number of copies of each kind of item and can be formulated as above except for that the only restriction on  is that it is a non-negative integer.

maximize 

subject to  and 

One example of the unbounded knapsack problem is given using the figure shown at the beginning of this article and the text "if any number of each box is available" in the caption of that figure.

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?”

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

Read also : Fractional Knapsack Problem With Solution

0/1 Knapsack Problem-

In 0/1 Knapsack Problem,

1. As the name suggests, items are indivisible i.e. we can not take the fraction of any item.
2. We have to either take an item completely or leave it completely.
3. It is solved using dynamic programming approach.

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

Consider we are given-

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

Step-01:

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

Step-02:

1. Start filling the table row wise top to bottom from left to right.
2. Use the following formula- T (i , j) = max { T ( i-1 , j ) , value_i + T( i-1 , j – weight_i ) }

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,

1. Considering the last column of the table, start scanning the entries from bottom to top.
2. 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.
3. After scanning all the entries, the marked labels represent the items that must be put in the knapsack.

Time Complexity

1. It takes θ(nw) time to fill (n+1)(w+1) table entries where each entry takes constant time θ(1) for its computation.
2. 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.
3. Thus, overall θ(nw) time is taken to solve 0/1 knapsack problem using dynamic programming approach.

PRACTICE PROBLEM BASED ON 0/1 KNAPSACK 

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.

OR

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

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?

Solution

Here given that

1. Knapsack capacity (w) = 5 kg
2. Number of items (n) = 4

Step-01:

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

Step-02:

Start filling the table row wise top to bottom from left to right using this following formula- T (i , j) = max { T ( i-1 , j ) , value_i + T( i-1 , j – weight_i ) }

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

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-

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

Identifying the items that must be put in the knapsack

1. Considering the last column, start scanning the entries from bottom to top.
2. 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,

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

Item-1 and Item-2

That's it. Hope it will help you.

Source Code

Hope it can help you!