0-1 Knapsack Problem


Python

Python : Dynamic programming solution to 0-1 knapsack problem implemented in Python3


C++ : Dynamic programming solution to 0-1 knapsack problem implemented in C++11

#include<vector>
#include<algorithm>

using namespace std;

// Recursive approach to 0-1 Knapsack problem
int Knapsack(vector<int> & weight, vector<int> & value, int numitems, int capacity){

    // 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(weight, value, numitems-1, capacity), // When the item is not included in the sack
                   Knapsack(weight, value, numitems-1, capacity-weight[numitems-1]) + value[numitems-1]); // When the item is included in the sack
    else
       return Knapsack(weight, value, numitems-1, capacity);
}

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

    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 (1, 3, 9) give maximum value of 21

    cout << "Maximum value of 0-1 Knapsack using DP : " << DPKnapsack(weight, value, capacity) << endl;
    cout << "Maximum value of 0-1 Knapsack using recursion: " << Knapsack(weight, value, weight.size(), capacity) << endl;

    vector<int> weight1 = {1, 2, 3, 5};
    vector<int> value1 = {1, 19, 80, 100};
    capacity = 6; // Item (1,5) gives maximum value of 101 

    cout << "Maximum value of 0-1 Knapsack using DP : " << DPKnapsack(weight1, value1, capacity) << endl;
    cout << "Maximum value of 0-1 Knapsack using recursion: " << Knapsack(weight1, value1, weight1.size(), capacity) << endl;

    vector<int> weight2 = {3, 5};
    vector<int> value2 = {80, 100};
    capacity = 2; // Item (1,5) gives maximum value of 101 

    cout << "Maximum value of 0-1 Knapsack using DP : " << DPKnapsack(weight2, value2, capacity) << endl;
    cout << "Maximum value of 0-1 Knapsack using recursion: " << Knapsack(weight2, value2, weight2.size(), capacity) << endl;

    vector<int> weight3 = {1, 2, 3, 4, 5};
    vector<int> value3 = {3, 5, 4, 8, 10};
    capacity = 5; // Items (1, 3, 9) give maximum value of 21

    cout << "Maximum value of 0-1 Knapsack using DP : " << DPKnapsack(weight3, value3, capacity) << endl;
    cout << "Maximum value of 0-1 Knapsack using recursion: " << Knapsack(weight3, value3, weight3.size(), capacity) << 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-2020, Algotree.org.
All rights reserved.