# 0-1 Knapsack Problem

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 : O ( n * m ), where n is the capacity of the knapsack and m is the number of weights available for putting into the knapsack.

Implementation of 0-1 knapsack problem

``````from typing import List # For annotations

# Recursive approach to 0-1 Knapsack problem
def Knapsack (numitems : int, capacity : List[int], weight : List[int], value : List[int]) -> int :
# 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 is not included.
Knapsack (numitems-1, capacity-weight[numitems-1], weight, value) + value[numitems-1] )# Item included.
else:
return Knapsack (numitems-1, capacity, weight, value)

# DP approach to 0-1 Knapsack problem
def DPKnapsack (capacity : List[int], weight : List[int], value : List[int]) -> int :

numitems = len(weight)
maxval = [0] * ( numitems + 1 )

for r in range ( numitems + 1 ) :
maxval[r] = [0] * ( capacity + 1 )

# If 0 items are put in the sack of capacity 'cap' then maximum value for each sack is 0
for cap in range ( capacity + 1 ) :
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 item in range ( numitems + 1 ) :
maxval[item][0] = 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
for item in range ( 1, numitems + 1 ) :
for cap in range ( 1, capacity + 1 ) :
if ( cap >= weight[item-1] ) :
maxval[item][cap] = max (maxval[item-1][cap], maxval[item-1][cap-weight[item-1]] + value[item-1])
else:
maxval[item][cap] = maxval[item-1][cap]

return maxval[numitems][capacity]

weight = [ [1, 2, 3, 4, 5],  [1, 3, 4, 6, 9],  [1, 2, 3, 5],     [3, 5] ]
value  = [ [3, 5, 4, 8, 10], [5, 10, 4, 6, 8], [1, 19, 80, 100], [80, 100] ]
capacity = [ 5, 10, 6, 2 ]

i = 0
while i <= 3:
print("\n[DP] 0-1 Knapsack max value : " + str ( DPKnapsack (capacity[i], weight[i], value[i])))
print("[Recursion] 0-1 Knapsack max valule : " + str( Knapsack (len(weight[i]), capacity[i], weight[i], value[i])))
i += 1
``````

Output

``````[DP] 0-1 Knapsack max value : 11
[Recursion] 0-1 Knapsack max valule : 11

[DP] 0-1 Knapsack max value : 21
[Recursion] 0-1 Knapsack max valule : 21

[DP] 0-1 Knapsack max value : 101
[Recursion] 0-1 Knapsack max valule : 101

[DP] 0-1 Knapsack max value : 0
[Recursion] 0-1 Knapsack max valule : 0
``````
``````#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<vector<int>> weight = { {1, 3, 4, 6, 9},  {1, 2, 3, 5},     {3, 5},    {1, 2, 3, 4, 5} };
vector<vector<int>> value  = { {5, 10, 4, 6, 8}, {1, 19, 80, 100}, {80, 100}, {3, 5, 4, 8, 10} };
vector<int> capacity       = { 10, 6, 2, 5 };

int i = 0;
// 4 test cases
while ( i <= 3) {
cout << "\n[DP] 0-1 Knapsack max value : " << DPKnapsack ( capacity[i], weight[i], value[i] ) << endl;
cout << "[Recursion] 0-1 Knapsack max value : " << Knapsack ( weight[i].size(), capacity[i], weight[i], value[i] ) << endl;
i++;
}

return 0;
}
``````

Output

``````[DP] 0-1 Knapsack max value : 21
[Recursion] 0-1 Knapsack max value : 21

[DP] 0-1 Knapsack max value : 101
[Recursion] 0-1 Knapsack max value : 101

[DP] 0-1 Knapsack max value : 0
[Recursion] 0-1 Knapsack max value : 0

[DP] 0-1 Knapsack max value : 11
[Recursion] 0-1 Knapsack max value : 11
``````
``````import java.util.Arrays;
import java.util.List;

class Main {

// Recursive approach to 0-1 Knapsack problem
static int Knapsack (int numitems, int capacity, List<Integer> weight, List<Integer> 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.get(numitems-1))
return Math.max (Knapsack (numitems-1, capacity, weight, value), // Item not included in the sack.
Knapsack (numitems-1, capacity-weight.get(numitems-1), weight, value) + value.get(numitems-1)); // Item included.
else
return Knapsack(numitems-1, capacity, weight, value);
}

// Dynamic programming approach to 0-1 Knapsack problem
static int DPKnapsack (int capacity, List<Integer> weight, List<Integer> value) {

int numitems = weight.size();
int maxval[][] = new int[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.get(item-1)) {
maxval[item][cap] = Math.max (maxval[item-1][cap], // Item not included in the sack.
maxval[item-1][cap-weight.get(item-1)] + value.get(item-1)); // Item included.
} else {
maxval[item][cap] = maxval[item-1][cap];
}
}
}
return maxval[numitems][capacity];
}

public static void main (String args[]) {

List<Integer> weight = Arrays.asList(1, 3, 4, 6, 9);
List<Integer> value = Arrays.asList(5, 10, 4, 6, 8);
int capacity = 10; // Items (1, 3, 9) give maximum value of 21

System.out.println("Maximum value of 0-1 Knapsack using DP : " + DPKnapsack(capacity, weight, value));
System.out.println("Maximum value of 0-1 Knapsack using recursion: " + Knapsack(weight.size(), capacity, weight, value));

List<Integer> weight1 = Arrays.asList(1, 2, 3, 5);
List<Integer> value1 = Arrays.asList(1, 19, 80, 100);
capacity = 6; // Item (1,5) gives maximum value of 101

System.out.println("Maximum value of 0-1 Knapsack using DP : " + DPKnapsack(capacity, weight1, value1));
System.out.println("Maximum value of 0-1 Knapsack using recursion: " + Knapsack(weight1.size(), capacity, weight1, value1));

List<Integer> weight2 = Arrays.asList(3, 5);
List<Integer> value2 = Arrays.asList(80, 100);
capacity = 2; // No item can be added to the knapsack.

System.out.println("Maximum value of 0-1 Knapsack using DP : " + DPKnapsack(capacity, weight2, value2));
System.out.println("Maximum value of 0-1 Knapsack using recursion: " + Knapsack(weight2.size(), capacity, weight2, value2));

List<Integer> weight3 = Arrays.asList(1, 2, 3, 4, 5);
List<Integer> value3 = Arrays.asList(3, 5, 4, 8, 10);
capacity = 5; // Items with weight (1, 4) give maximum value of 11.

System.out.println("Maximum value of 0-1 Knapsack using DP : " + DPKnapsack(capacity, weight3, value3));
System.out.println("Maximum value of 0-1 Knapsack using recursion: " + Knapsack(weight3.size(), capacity, weight3, value3));

}
}
``````

Output

``````Maximum value of 0-1 Knapsack using DP : 11
Maximum value of 0-1 Knapsack using recursion: 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
``````