How to solve a 0/1 Knapsack Problem using Dynamic Programming?

A knapsack problem is a problem in combinatorial optimization in which the goal is to find the most efficient way to fill a knapsack with a given set of items. Each item has a specific weight and value, and the goal is to fill the knapsack with as much value as possible while keeping the total weight below a given limit.

The problem can be solved using a variety of algorithms, such as dynamic programming, greedy algorithms, and branch and bound. However, the most efficient algorithm for solving the problem depends on the specific instance of the problem and the amount of time and computational resources available.

This problem is a classic example of a combinatorial optimization problem and has been studied extensively by mathematicians and computer scientists. Many real-world problems can be formulated as a Knapsack problem, such as resource allocation, packaging, and manufacturing. Unfortunately, it is also NP-complete, meaning that no known algorithm can solve all instances of the problem in polynomial time.

There are mainly two types of Knapsack problems.

1. 0/1 Knapsack Problem
2. Fractional Knapsack Problem

In this part, we’ll solve the 0/1 Knapsack and in the next part, we’ll solve the fractional knapsack problem.

0-1 Knapsack Problem:

In the 0-1 Knapsack problem, the main statement remains the same, i.e. we’ve to maximise the value within the given weight. But in this case, we have a condition that we can pick either the complete element or nothing. We can’t pick a fraction of the element.

For example, see this image below-

Now solving this problem using Dynamic programming is a more general approach. This approach typically involves solving a series of sub-problems and then combining the solutions to these sub-problems to find the solution to the original problem.

There are two main steps in the dynamic programming approach:

1. Determine the order in which the sub-problems should be solved.
2. Solve the sub-problems and combine the solutions to find the solution to the original problem.

The order in which the sub-problems are solved is important, as it will determine the amount of work that needs to be done. In the 0-1 Knapsack Problem, the sub-problems can be solved in either a top-down or bottom-up fashion.

Once the order in which the sub-problems should be solved has been determined, the sub-problems can be solved using a recursive or iterative approach.

A recursive approach involves solving the sub-problem for the first item, then solving the sub-problem for the second item, and so on until the solution to the original problem is found.

An iterative approach would start by solving the sub-problem for the small items, then the medium items, and finally the large items.

Let’s understand the problem with the code and explanation.

Code:

// solution for 0-1 Knapsack problem
#include <stdio.h>
int max(int a, int b)
{
	return (a > b) ? a : b;
}
/* Returns the maximum value that can be put in the bag */
int knapSack(int W, int wt[], int prof[], int n)
{
	int i, w;
	int K[n + 1][W + 1];

	for (i = 0; i <= n; i++)
	{
		for (w = 0; w <= W; w++)
		{
			if (i == 0 || w == 0)
				K[i][w] = 0;
			else if (wt[i - 1] <= w)
				K[i][w] = max(prof[i - 1] + K[i - 1][w - wt[i - 1]],
							  K[i - 1][w]);
			else
				K[i][w] = K[i - 1][w];
		}
	}

	return K[n][W];
}

int main(void)
{
	int W, n, i;
	float prof[100], wt[100];
	float wp[100];
	printf("Weight Limit: ");
	scanf("%d", &W);
	printf("Total number of stones-\n");
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		printf("Weight & Corresponding profit-\n");
		scanf("%d%d", &wt[i], &prof[i]);
	}
	printf("Maximum Value is- %d", knapSack(W, wt, prof, n));
}

Input:

For input, let’s take the same example of bag and stone.

Weight Limit: 8
Total number of stones-
4
Weight & Corresponding profit-1200
Weight & Corresponding profit-
2
400
Weight & Corresponding profit-
4
100
Weight & Corresponding profit-
3
500

Output:

Maximum Value is- 1100

Explanation:

To solve the 0/1 Knapsack Problem using Dynamic Programming, we need to create a table first containing the values and the weights.

1. First, create a table with the required weight and number of items.
2. Then make another table of weights with their corresponding values.
3. Then put values according to the weights.

Follow these steps to find out the solution to this problem.

Time Complexity:

The 0/1 knapsack problem is a classic dynamic programming problem that has a time complexity of O(nW), where n is the number of items and W is the capacity of the knapsack.

See the video-

So that’s all for this blog.

Hope you find this blog useful, if yes then please share this with your friends too and if you want to add anything, you can comment below.

See you in the next blog.