0-1 Knapsack Using C++

Filed Under: C++
0 1 Knapsack Using 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.

Knapsack Problem
Knapsack Problem

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)).
Repeating Subproblems
Repeating Subproblems

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)
Knapsack Pseudocode
Knapsack Pseudocode

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,

0 1 Knapsack
0-1 Knapsack

Output

0 1 Knapsack Output
0-1 Knapsack Output

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.

Further Reading

To learn more about knapsacks, you can refer to the following websites.

https://en.wikipedia.org/wiki/Knapsack_problem

close
Generic selectors
Exact matches only
Search in title
Search in content