The 0-1 knapsack programming problem is as below:

Given.

a) A finite collection of weights with values.

b) An empty knapsack with a limited weight capacity.

The goal is to **maximize the value of the knapsack** by adding chosen weights that the knapsack can hold.

**Example:**

Say we have a knapsack of **capacity 5** kg.

And we have a **set of available items** with their weights and corresponding values: **[ 1 kg - $3 ], [ 2 kg - $5 ], [ 3 kg - $4 ], [ 4 kg - $8 ] and [ 5 kg - $10 ]**

Thus the set of available items/weights is :

Item | Weight | Value |
---|---|---|

1. | 1 kg |
$ 3 |

2. | 2 kg | $ 5 |

3. | 3 kg | $ 4 |

4. | 4 kg |
$ 8 |

5. | 5 kg | $ 10 |

We can see that adding weights 1 kg (value $ 3) and 4 kg (value $ 8) to the knapsack gives it maximum value of $ 11.

__Recurrence relation for the 0-1 knapsack__

Base cases:

- If the capacity of the sack is
**0 kg**, then no item can be added to the knapsack. Thus

**0-1 Knapsack (numitems, capacity = 0, weight, value) = 0**; when capacity equals 0. - If
**zero items**are available for filling the knapsack, then none can be put into the knapsack

**0-1 Knapsack (numitems = 0, capacity, weight, value) = 0**; when the number of items equal 0.

- If the available capacity of the knapsack is greater than the weight of the chosen item to be put,

check what would give a higher value to the knapsack

A knapsack**not containing**the chosen item. Thus the number of items now available is reduced by 1.

**or**

A knapsack**containing**the chosen item. Thus the capacity of the knapsack is reduced by the weight of the item, but

the value of the knapsack is increased by the value of the chosen item.

Thus we have,

**0-1 Knapsack (numitems, capacity, weight, value) =**

**maximum ( 0-1 Knapsack (numitems - 1, capacity, weight, value) or**

**0-1 Knapsack (numitems - 1, capacity - weight [ numitems -1 ], weight, value) + value[ numitems-1 ] ) )**

__Dynamic programming approach for 0-1 knapsack__

**Base case values for 0-1 knapsack**

Knapsack Capacity 0 kg | Items | Value of knapsack | Hint |
---|---|---|---|

0 kg | 0 kg, 1 kg, …, 5 kg | $0 | The knapsack of capacity 0 kg cannot hold any item. |

Knapsack Capacity 5 kg | Items with weight 0 kg | Value of knapsack | Hint |
---|---|---|---|

1 kg | 0 kg | $0 | Item of weight 0 kg does not add any value to the knapsack. |

… … … |
0 kg | $0 | Item of weight 0 kg does not add any value to the knapsack. |

5 kg | 0 kg | $0 | Item of weight 0 kg does not add any value to the knapsack. |

**Note:** A weight of 0 kg of value $ 0 is added to the DP table for handling the base cases.

Filling the values in the dynamic programming table of 0-1 Knapsack using recurrence.

**Recurrence equation for 0-1 Knapsack**

0-1 Knapsack (numitems, capacity) =
Max ( 0-1 Knapsack (numitems - 1, capacity) **or**

0-1 Knapsack (numitems - 1, capacity - weight [ numitems -1 ]) + value [ numitems-1 ] ) )

**Example:**

Consider filling the knapsack of **capacity 5 kg** with items of **weight 0 kg ( $ 0 ), 1 kg ( $ 3 ), 2 kg ( $ 5 ), 3 kg ( $ 4 ) and 4 kg ( $ 8 ).**

i.e Filling value in table [4] [5]

The maximum value of the knapsack of capacity **5 kg** = maximum of ( __value of knapsack using weights (0 kg, 1 kg, 2 kg, 3 kg )__ **or** __value of knapsack when a weight of 4 kg is chosen along with any of the chosen weights from ( 0 kg, 1 kg, 2 kg, 3 kg)__

From the table,

- Maximum value of the knapsack of capacity 5 kg by choosing weights from ( 0 kg, 1 kg, 2 kg, 3 kg ) =
**$ 9**. - After we put a weight of 4 kg into the knapsack, the
**capacity of the knapsack is reduced to 1 kg (5 kg - 4 kg)**and the**value is increased to $ 8**.

The reduced capacity of 1 kg of the knapsack should be filled by choosing weight(s) from ( 0 kg, 1 kg, 2 kg, 3 kg ). - From the table we see that the maximum value of the knapsack of capacity 1 kg when choosing weight(s) available from ( 0 kg, 1 kg, 2 kg, 3 kg ) is
**$ 3**.

Thus, we get

table [ 4 ] [ 5 ] = max ( table [ 3 ] [ 5 ] **or** table [ 3 ] [ 5 - 4 ] + value of weight [ 4 kg ] ) i.e

table [ 4 ] [ 5 ] = max ( $ 9 or $ 3 + $ 8 ) i.e

the maximum Value of knapsack of capacity 5 kg = maximum of ( $9, $3 + $8) = $11.

**Time complexity of 0-1 knapsack : O(n*m)**, where **n** is the capacity of the knapsack and **m** is the number of weights available for putting into the knapsack.

**Java**

**Python**

**0-1 knapsack problem in C++.**

```
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// Recursive approach to 0-1 Knapsack problem
int Knapsack (int numitems, int capacity, vector<int> & weight, vector<int> & value) {
// No item can be put in the sack of capacity 0 so maximum value for sack of capcacity 0 is 0
if (capacity == 0)
return 0;
// If 0 items are put in the sack, then maximum value for sack is 0
if (numitems == 0)
return 0;
/* Note : Here the number of item is limited (unlike coin change / integer partition problem)
hence the numitems -> (numitems - 1) when the item is included in the knapsack */
if (capacity >= weight[numitems-1])
return max (Knapsack (numitems-1, capacity, weight, value), // item not included in the sack
Knapsack (numitems-1, capacity-weight[numitems-1], weight, value) + value[numitems-1]); // Item included.
else
return Knapsack(numitems-1, capacity, weight, value);
}
// Dynamic programming approach to 0-1 Knapsack problem
int DPKnapsack (int capacity, vector<int> & weight, vector<int> & value) {
int numitems = weight.size();
int maxval[numitems+1][capacity+1];
// If 0 items are put in the sack of capacity 'cap' then maximum value for each sack is 0
for (int cap=0; cap<=capacity; cap++)
maxval[0][cap] = 0;
// No item can be put in the sack of capacity 0 so maximum value for sack of capcacity 0 is 0
for (int item=0; item<=numitems; item++)
maxval[item][0] = 0;
for (int item=1; item <= numitems; item++) {
for (int cap=1; cap <= capacity; cap++) {
/* Note : Here the number of item is limited (unlike coin change / integer partition problem)
hence the numitems -> (numitems - 1) when the item is included in the knapsack */
if (cap >= weight[item-1]) {
maxval[item][cap] = max (maxval[item-1][cap], // Item not included in the knapsack
maxval[item-1][cap-weight[item-1]] + value[item-1]); // Item included in the knapsack
} else {
maxval[item][cap] = maxval[item-1][cap];
}
}
}
return maxval[numitems][capacity];
}
int main() {
vector<int> weight = {1, 3, 4, 6, 9};
vector<int> value = {5, 10, 4, 6, 8};
int capacity = 10; // Items with weight (1, 3, 9) give maximum value of 21
cout << "Maximum value of 0-1 Knapsack using DP : " << DPKnapsack(capacity, weight, value) << endl;
cout << "Maximum value of 0-1 Knapsack using recursion: " << Knapsack(weight.size(), capacity, weight, value) << endl;
vector<int> weight1 = {1, 2, 3, 5};
vector<int> value1 = {1, 19, 80, 100};
capacity = 6; // Item with weight (1,5) gives maximum value of 101
cout << "Maximum value of 0-1 Knapsack using DP : " << DPKnapsack(capacity, weight1, value1) << endl;
cout << "Maximum value of 0-1 Knapsack using recursion: " << Knapsack(weight1.size(), capacity, weight1, value1) << endl;
vector<int> weight2 = {3, 5};
vector<int> value2 = {80, 100};
capacity = 2; // No item can be added to the knapsack.
cout << "Maximum value of 0-1 Knapsack using DP : " << DPKnapsack(capacity, weight2, value2) << endl;
cout << "Maximum value of 0-1 Knapsack using recursion: " << Knapsack(weight2.size(), capacity, weight2, value2) << endl;
vector<int> weight3 = {1, 2, 3, 4, 5};
vector<int> value3 = {3, 5, 4, 8, 10};
capacity = 5; // Items with weight (1 and 4) give maximum value of 11
cout << "Maximum value of 0-1 Knapsack using DP : " << DPKnapsack(capacity, weight3, value3) << endl;
cout << "Maximum value of 0-1 Knapsack using recursion: " << Knapsack(weight3.size(), capacity, weight3, value3) << endl;
return 0;
}
```

Output of 0-1 knapsack problem implemented in C++11

```
Maximum value of 0-1 Knapsack using DP : 21
Maximum value of 0-1 Knapsack using recursion: 21
Maximum value of 0-1 Knapsack using DP : 101
Maximum value of 0-1 Knapsack using recursion: 101
Maximum value of 0-1 Knapsack using DP : 0
Maximum value of 0-1 Knapsack using recursion: 0
Maximum value of 0-1 Knapsack using DP : 11
Maximum value of 0-1 Knapsack using recursion: 11
```

All rights reserved.