0-1 Knapsack Problem

#!/usr/bin/python3

# Recursive approach to 0-1 Knapsack problem
def Knapsack(weight, value, numitems, 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)

# DP approach to 0-1 Knapsack problem
def DPKnapsack (weight, value, capacity) :

    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(weight, value, capacity)))
print("Maximum value of 0-1 Knapsack using recursion: "+str(Knapsack(weight, value, len(weight), capacity)))

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(weight, value, capacity)))
print("Maximum value of 0-1 Knapsack using recursion: "+str(Knapsack(weight, value, len(weight), capacity)))

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(weight, value, capacity)))
print("Maximum value of 0-1 Knapsack using recursion: " +str(Knapsack(weight, value, len(weight), capacity)))

weight = [3, 5]
value = [80, 100]
capacity = 2; # Item (1,5) gives maximum value of 101

print("Maximum value of 0-1 Knapsack using DP : "+str(DPKnapsack(weight, value, capacity)))
print("Maximum value of 0-1 Knapsack using recursion: " + str(Knapsack(weight, value, len(weight), capacity)))

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

#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;
}

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