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.

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

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.

Consider we are given-

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

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

- 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 }) }

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

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

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.

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

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.

Item |
Weight |
Value |

1 | 2 | 3 |

2 | 3 | 4 |

3 | 4 | 5 |

4 | 5 | 6 |

**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)

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?

Item |
Weight (kg) |
Value ($) |

Mirror | 2 | 3 |

Silver nugget | 3 | 4 |

Painting | 4 | 5 |

Vase | 5 | 6 |

Here given that

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

- 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 0
^{th}row and 0^{th}column with 0.

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-

- 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

- 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**

That's it. Hope it will help you.

Hope it can help you!

#greedy-algorithm #0-1-knapsack