# 0-1 Knapsack Using C++

Filed Under: C++ In this article, we will look at the solution to 0-1 knapsack using C++. 0-1 Knapsack is one of the most popular problems in the programming world. In this article, we will look at the dynamic programming-based solution to this problem. So, without any further delay, let’s quickly read and understand the problem statement.

Also read: Fractional Knapsack Using C++

## Problem Statement

You are given the weights and prices of N items and a knapsack of capacity W. You have to fill the knapsack in such a manner that the value of the items selected is maximum. Also, you can select an item only once.

It is a problem in the combinatorial optimization domain. We often encounter this problem in our daily lives when we have a fixed budget or have some time constraints and a range of items to select from. The naive approach to this problem is inefficient i.e. either we select the item or we don’t, hence we look at all the possible combinations and end up with an exponential order complexity.

## Pseudocode

The most important rule to keep in mind while writing the algorithm is that,

• The ith item from the list may either be used or not, hence for a particular subproblem we select the maximum of the values if it is selected or it is not selected.
• The value after selecting the ith item is: `value(W - wi, i - 1) + vi`.
• The value if we don’t select the ith item will be: `value(W, i - 1)`.
• Value(w, i) is evaluated as: `max(value(W - wi, i - 1) + vi, value(W, i - 1))`.

Let’s look at the pseudocode of the knapsack algorithm, below at the steps that we will follow while writing the code.

• W <- Represents the maximum capacity of the knapsack
• w <- Represents the current weight of the knapsack under consideration
• wi <- Represents the weight of the ith item
• Initialize the dynamic programming array to store the answer to repeating subproblem as described below:
• all `value(0, j) <- 0`
• all `value(w, j) <- 0`
• Start a for loop that will run from `i = 1` to `i = N`
• Start an inner for loop that will run from `w = 1` to `w = W`
• `value(w, i) <- value(w, i - 1)`
• `if(wi <= w)`
• `val <- value(w - wi, i - 1) + vi`
• `if(value(w, i) < val)`
• `value(w, i) <- val`
• `return val(W, N)`

## 0-1 Knapsack Code Using C++

```#include <iostream>
#include <vector>

using namespace std;

void knapsack(vector <int> weights, vector <int> prices, int W)
{
// initialize the dp vector
int len = weights.size();
vector <vector <int>> value(W + 1, vector <int> (len + 1, 0));

for(int i = 1; i <= len; i++)
{
for(int w = 1; w <= W; w++)
{
value[w][i] = value[w][i - 1];

if(weights[i - 1] <= w)
{
int val = value[w - weights[i - 1]][i - 1] + prices[i - 1];
if(value[w][i] < val)
value[w][i] = val;
}
}
}

cout << "The values vector is:" << endl;

for(int i = 0; i <= W; i++)
{
for(int j = 0; j <= len; j++)
cout << value[i][j] << " ";
cout << endl;
}

cout << "The maximum profit: " << value[W][len] << endl;
}

int main()
{
cout << "Enter the weights of the items, press -1 to stop" << endl;

vector <int> weights;

while(true)
{
int weight;
cin >> weight;

if(weight == -1)
break;

weights.push_back(weight);
}

cout << "Enter the values of each item, press -1 to stop" << endl;

vector <int> values;

while(true)
{
int value;
cin >> value;

if(value == -1)
break;

values.push_back(value);
}

cout << "Enter the capacity of the knapsack" << endl;

int capacity;
cin >> capacity;

knapsack(weights, values, capacity);
}
```

Let’s consider the following example,

## Time And Space Complexity Analysis

The overall time complexity of the algorithm is: `O(N.W)`. This is because of two nested for loops, of which the outer loop runs N times and the inner loop runs W times for each iteration of the outer for loop.

The space complexity is also `O(N.W)` because we are using a 2-dimensional matrix for storing intermediate states.

## Conclusion

Today we learned to implement the 0-1 knapsack algorithm using C++. In the beginning, we discussed the problem statement, and then we moved to the pseudocode of the algorithm. Later we wrote a C++ program to demonstrate this algorithm. That’s all for now, thanks for reading.