Solving the 0-N Knapsack Problem In C++

Filed Under: Java
0 N Knapsack Problem In C

In this article, we will be learning an efficient approach to the 0-N knapsack problem in C++. This problem is one of the most popular classic dynamic programming problems. Though we can also solve this problem using a recursive approach in this article, we will only cover the dynamic programming solution to this problem.

0-N Knapsack Problem

It is just a slight modification to the 0-1 knapsack problem.

Problem Statement

There is a list of N items that contains their prices and weights. You are given a bag of finite capacity say W, you have to fill the bag in such a manner that the total price of items in the bag is maximum among all the possible combinations. Assume that there is an infinite supply of every item and you can choose any item any number of times.

The problem is very straightforward but its solution is a little tricky. The naive recursive approach will directly lead us to a very inefficient path because it involves investigation and comparing all the possible solutions and choosing the best. This means that for N items there are going to be 2N total combinations, and going through all these combinations is an exponential complexity task. This idea limits the computation to a maximum of 15-20 items. However, this is very poor complexity and it has almost no use in real-life cases. Hence we need something better. Let’s move to the dynamic programming approach to tackle this problem more efficiently.

0 N Knapsack
0-N Knapsack

Knapsack Algorithm Using Dynamic Programming

Since it is a maximization problem, we can approach this by using a 1-dimensional DP(Dynamic Programming) array. Dynamic programming is very useful when we have recurring subproblems. And in the knapsack, there are a lot of repeating subproblems. Hence, we create an array to store the solution to all the subproblems. Below is an example to clarify your understanding.

Maximum weight allowed: W = 20kg

Weights = {5, 10, 15}

Values = {10, 30, 20}

Possible combinations of weights and values:

  1. {5, 5, 5, 5}
  2. {10, 10}
  3. {10, 5, 5}
  4. {15, 5}

Notice that in cases 1 and 3 we have repeating subproblems after selecting {5, 5} and {10}, because now we select the same combination of {5, 5} again. To avoid repeated calculations of these subproblems we use dynamic programming.

Steps to solve knapsack are:

  • Initialize an array of size W + 1 with 0.
  • Each cell of this array represent the possible weights of the bag from 0 to W.
  • We optimize the value for each weight and build this array in a bottom-up manner
  • The last element of this array will contain the maximum value for the weight W.

Let’s see how to fill the array

  • Start a for loop to traverse over all the indices of the array i.e. from 0 to N
  • Now for each value of weight, we start another for loop for each weight
    • This inner for loop moves over all the N items
    • If the weight of current item under consideration is less than i(representing current weight) then we will simply drop this item for current value of i.
    • Otherwise the weight will be: max(dp[i - arr[j] + value[i], dp[i])

That’s basically it for the algorithm, once we are out of both the loops we return the last element of the array i.e return arr[W]. Let’s quickly jump to the code and see the working of the algorithm.

Code to Solve the 0-N Knapsack Problem In C++

#include <iostream>
#include <vector>

using namespace std;

int knapsack(vector <int> weights, vector <int> values, int W)
{
	// initializing the dp array
	vector <int> dp(W + 1, 0);

	for(int i = 0; i < W + 1; i++)
	{
		//cout << "Evaluating for the weight: " << i << endl;

		for(int j = 0; j < weights.size(); j++)
		{
			//cout << "Index: " << j << endl;
			//cout << "Weight at this index: " << weights[j] << endl;

			// consider the current element
			// only if its weight is less than
			// the current weight under consideration
			if(weights[j] <= i)
			{
				int curr_value = dp[i];
				//cout << "Value at this index: " << values[j] << endl;
				//cout << "Current maximum value for weight: " << i << " is: " << dp[i] << endl;
				// now is the logic to
				// maximize the weight
				dp[i] = max(dp[i - weights[j]] + values[j], dp[i]);
				//if(dp[i] != curr_value)
					//cout << "After this comparision the value increased from: " << curr_value << " to: " << dp[i] << endl;
			}
		}
	}

	cout << "The subproblem array is:" << endl;

	for(int value : dp)
		cout << value << " ";
	
	cout << endl;
	cout << "Maximum profit for current list of items is: " << dp[W] << endl;

	return dp[W];
}

int main()
{
	vector <int> weights;
	cout << "Enter the weights of items |Press -1 to stop|" << endl;
	
	while(true)
	{
		int weight;
		cin >> weight;

		if(weight == -1)
			break;
		weights.push_back(weight);
	}

	vector <int> values;
	cout << "Now enter the value of each item |Press -1 to stop|" << endl;

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

		if(value == -1)
			break;

		values.push_back(value);
	}

	cout << "Enter the target weight" << endl;

	int W;
	cin >> W;

	knapsack(weights, values, W);
}
0 N Knapsack Algorithm Code
0-N Knapsack Algorithm Code

Notice that in the picture attached above, the code contains several cout statements i.e. console output statements, the purpose of these statements is to help you understand each and every step of the code. While running this code, you can uncomment these statements and then compile the program, then running this program will give detailed information for the algorithm.

Driver Code
Driver Code

Output

0 N Knapsack Program Output
0-N Knapsack Program Output

Conclusion

In this article, we learned to implement the algorithm for the 0-N knapsack problem. We used the dynamic programming approach. The outer for loop runs W times and the inner for loop runs N times for each iteration of the outer for loop. Hence the effective time complexity for the algorithm got deduced to O(N.W). That’s all for today, thanks for reading.

Further Readings

To learn more about dynamic programming and popular algorithms, you can refer to the following websites.

https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/tutorial/

https://leetcode.com/discuss/interview-question/1282577/selling-wine-dp-easy-c

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