0-1 Knapsack Problem
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 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
0-1 knapsack problem in Java.
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
Python
0-1 knapsack problem in Python.
#!/usr/bin/python3
# Recursive approach to 0-1 Knapsack problem
def Knapsack (numitems, capacity, weight, 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 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, weight, value):
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]
value = [3, 5, 4, 8, 10]
capacity = 5; # Items (1, 3) give maximum value of 11
print("Maximum value of 0-1 Knapsack using DP : " + str( DPKnapsack (capacity, weight, value)))
print("Maximum value of 0-1 Knapsack using recursion: " + str( Knapsack (len(weight), capacity, weight, value)))
weight = [1, 3, 4, 6, 9]
value = [5, 10, 4, 6, 8]
capacity = 10; # Items (1, 3, 9) give maximum value of 21
print("Maximum value of 0-1 Knapsack using DP : " + str( DPKnapsack (capacity, weight, value)))
print("Maximum value of 0-1 Knapsack using recursion: " + str( Knapsack (len(weight), capacity, weight, value)))
weight = [1, 2, 3, 5]
value = [1, 19, 80, 100]
capacity = 6; # Item (1,5) gives maximum value of 101
print("Maximum value of 0-1 Knapsack using DP : " + str( DPKnapsack (capacity, weight, value)))
print("Maximum value of 0-1 Knapsack using recursion: " + str( Knapsack (len(weight), capacity, weight, value)))
weight = [3, 5]
value = [80, 100]
capacity = 2; # // No item can be added to the knapsack.
print("Maximum value of 0-1 Knapsack using DP : " + str( DPKnapsack (capacity, weight, value)))
print("Maximum value of 0-1 Knapsack using recursion: " + str( Knapsack (len(weight), capacity, weight, value)))
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
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
Copyright (c) 2019-2021, Algotree.org.
All rights reserved.