Algotree > Algorithms > Dynamic Programming > 0-1 Knapsack Problem

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	Value of knapsack	Hint
1 kg	$0	Item of weight 0 kg does not add any value to the knapsack.
… … …	$0	Item of weight 0 kg does not add any value to the knapsack.
5 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.

01_Knapsack_Base_Case_Table

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

# 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],  [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