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

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
``````