0/1 Knapsack Problem

Let us suppose we had that have certain weights, we need to put them in a knapsack in such a way that they produce the maximum profit, the knapsack can be thought of as a container. 

Suppose we have a container that weighs 50 kg, we need to place the weights in such a way that it is either lesser than or equal to the weight of the container, and the profit is maximum. 

Knapsack problems are divided into two categories:

1. 0/1 knapsack problem, which we will be discussing,
2. Fractional knapsack problem. 

what is the 0/1 knapsack problem?

In the 0/1 knapsack problem, the items are either completely filled in a knapsack, or not filled at all. For better understanding, assume we have a weight of 2 kg, so if we pick that item, we will have to pick the entire 2 kg, we cannot pick 1 kg from the 2 kg item, as it will not be divisible. So, we will either have to pick this item completely or not pick it at all.

This is referred to as the knapsack problem. 

Example:

Let us discuss the following example for better understanding,

let us consider the following weights: {3,4,5,6}

And the following profits: {1,2,3,4}

And let the weight of the knapsack be 8 kg.

And, the number of allowed items is 4. 

We will solve the problem using the following method:

Possible combinations for xi= {0,1,0,1}, {0,0,0,1}, {1,0,0,1}

So the total number of combinations for the given problem = 2^n = 2^4 = 16. 

n represents the total number of items that can be selected. So, we can have a total of 16 combinations for the example we have taken. 

We one by one try all the possible combinations and choose the one that maximizes the profit. 

Solving it using the dynamic method. 

Another method to solve the example will be to use the dynamic approach. 

So we begin by creating a matrix as follows:

We have columns from 0 to 8, as the weight is 8 kgs. 

And the rows extend from 0 to 4, as the maximum number of items allowed is 4. 

This way we have divided the problem into sub-problems, where we will be solving each cell individually. 

We begin by writing the weights in their ascending order, and the profits adjacent to the weights, so it will be as follows:

Wi = {3,4,5,6}

Pi= {2,3,4,1} 

So the matrix for when i=1, and weight = 1 will be:

Explanation:

When i=1, weight is 3 kgs, but the allowed weight for the knapsack is only 1 kg, so we cannot pick the 3 kgs, and hence we put a 0. 

Similarly, we construct the matrix for i=1,2,3,4 , and W=1,2,3,4,5,6,7,8. 

Reference

0/1 Knapsack Problem