Critical Analysis Of 0–1 Knapsack

Introduction

In this post I’d want to describe and show a very famous algorithm, 0–1 Knapsack, but before we do, it’s important to understand what dynamic programming is and why we’re using it here rather than using another technique. In basic terms, dynamic programming is the process of optimizing a recursive algorithm, for understanding it let’s consider an algorithm that calls the same function and supplies it with the same input(s). In this instance, we choose to use dynamic programming to optimize the algorithm. In other words, the primary purpose is to save the solution of subproblems; This is done to prevent re-computation of the same subproblems later on in the algorithm’s iteration. The optimization approach enables us to lower the time complexity of the algorithm from exponential to polynomial, isn’t that amazing!

Let’s Understand What is 0–1 Knapsack?

Assume we are given a bag or a knapsack capable of carrying a total weight “W,” as well as a collection of goods or items with their respective weights and costs/profits. Our ultimate objective is to increase the overall number of products in order to maximize earnings while also entirely filling the backpack/knapsack. Now, in terms of coding, examine the weights and values of n elements in order to maximize the total value of the knapsack. To perform this task we take two integer arrays, val[0..n-1] and wt[0..n-1], which are used to represent/denote the values and weights associated with n items. We then proceed to find the greatest value subset of val[] such that the sum of its weights is less than or equal to W, and given an integer W denoting a knapsack’s maximum capacity. Additionally, we have the restriction that we cannot break an object; we must either pick it up entirely or not at all. This is attribute is referred to as the 0–1 property.

Methods We Can Use

There are 2 methods to tackle the 0–1 knapsack problem;

· Method 1: Using Recursion By Brute Force.

· Method 2: By using Dynamic Programming.

Approach For Method 1:

The straightforward method is to examine all subgroups of items and determine their combined weight and worth. Consider the subgroups with a total weight less than W. Select the subset with the greatest value from all of these subsets.

Optimal Sub-structure: To consider all subsets of items, there can be two cases for every item.

From here we have 2 cases to check whether our item fits in the Optimal Sub-structure Or Not:

Case 1: The item can be included in the optimal subset.

Case 2: The item cannot be included in the optimal set.

As a result, the greatest value that can be produced from ’n’ items is equal to the sum of the next two values.

The maximum value that may be engendered with “n-1” items and a weight of W (omitting “nth” item). The value of the “nth” item multiplied by the greatest value procured by the “n-1th” item, and W minus the “nth” item’s weight (including the “nth” item). If the weight of the “nth” item is more sizably voluminous than the weight of the ‘W’ item, the “nth” item cannot be integrated, leaving just Case 1 as our only choice.

Approach For Method 2:

As with other classic Dynamic Programming (DP) algorithms, re-computation of identical subproblems may be avoided by bottom-up construction of a temporary array DP[][]. The implementation that follows is based on Dynamic Programming.

In dynamic programming, we will investigate the same scenarios as in recursive programming. Consider the columns of a DP[][] table to be all potential weights ranging from ‘1’ to ‘W’, and the rows to be all possible weights. The state DP[i][j] denotes the greatest value of ‘j-weight’ when all values between ‘1 and ith’ are considered. Thus, if we examine ‘wi’ (weight in the ‘ith’ row), we may use it to populate all columns with ‘weight values greater than wi’.

Now, two scenarios are possible:

Conditions For Dynamic Approach

· Fill in the blank column with ‘wi’.

· Leave ‘wi’ blank in the selected column.

Now we must choose the most favorable of these two alternatives; officially, if we do not fill the ‘ith’ weight in the ‘jth’ column, the DP[i][j] state will be identical to DP[i-1][j], but if we do, DP[i][j] will equal the value of ‘wi’ + the value of the column weighing ‘j-wi’ in the preceding row. Thus, we maximize one of these two options in order to fill the present state.

Solved Example:

To better understand the concept of 0–1 knapsack we are going to compute to solution of the following example; Consider two integer arrays val[] = {1,2,5,6}; wt[] = {2,3,4,5}. Using these 2 arrays we can determine 2 things the rows and the columns of the table i.e., number of rows is equal to the number of weights and number of columns is equal to the sum of the size of both the arrays i.e., val[] and wt[]. Now that we know the total number of rows and columns that need to be constructed in order to use 0–1 knapsack in this example lets construct our table.

Steps to implement 0–1 knapsack:

1. Construct a table of “i” rows and “j” columns where i = Number of elements in val[] array and j = Number of elements in val[] + Number of elements in wt[].

2. Now using a little bit of common sense, we know one thing for sure that no item can have a weight value of 0, therefore we have assigned the value 0 to the 0th row and 0th column(See image 1 for better understanding).

Image 1

3. Now moving on the 1st row, we check for the weight value assigned to this row which turns up to be 2 so now we look for a value in the column (knapsack capacity) section which could accept/carry the weight of that particular row so the pointer goes from 0 to 8th column we know that a knapsack with weight carrying capacity W = 2 can carry a weight w = 2, so in that respective slot we enter that weight’s respective profit or value which in this case is 1. Now we know that when W = 2 we can carry an object of weight 2 so this directly implies that if W≥2 we can put it in the knapsack, hence we assign profit of w = 2 to all other slots of that row but while doing this we have to keep one thing in mind that we have to check for the profit of the previous row for the remainder of the column number and weight w i.e., j-wi. But for now, we can simply write 1 or the profit of 2(wi) because j- wi = 0 or the entries of the previous rows will be 0. (See image 2 for better understanding).

Image 2

4. Now let’s move onto the 2nd row, following the same steps as 1st row we simply use the values entered in the previous rows for their respective columns for example K(2,1) will be 0 since 3(wi) cannot fit in 1(W), similarly K(2,2) will be 1 since 3(wi) cannot fit in 2 but the previous entry of wi can easily fit in 2(W). Now, when wi = W i.e., both are 3 we can put the profit of wi or 3 in K(2,3) which is 2. From this point on we know that W≥wi i.e., we are sure that the knapsack can carry weight of 3 from this point but we would have to check for the remainder as well because our end condition was to maximize the capacity of the knapsack so we compute j-wi and find out the total profit for example let’s take j to be column 5 so j-wi becomes 5–2=3 so we look at the 3rd column in the i-1th row i.e., 3–1 = 2nd row, so the value of column 3 in row 2 is 1 so the updated profit or value becomes 2+1=3. Therefore our new profit is 3, we follow the same procedure for the rest of the entries in that row.

Image 3

5. For the 3rd row we follow the same steps mentioned above(see image 4 reference)

Image 4

6. Now we move onto the last row of the table in this row we find our answer, to reach there we have to follow the same steps we followed for the rest of the rows. Once we compute the entire table we have to look for unique values in different rows and those unique values should not be inherited from the previous row, in row 4 value 8 is unique and is not inherited from any other row, now we look for the profit associated with that row which is 6 so 8–6 i.e., Unique value — Pi will give us the remaining value of our knapsack which is 2 so now we need to find where 2 is located and is unique in the table. We can see 2 is present in the above row i.e., 3rd row but is not unique since it is inherited from row 2 so we look in row 2 and there we find that value 2 is unique so we can use it to satisfy our condition of maximizing the knapsack, now our knapsack is full since we’ve satisfied the condition of maximizing the capacity whilst achieving maximum profit.

Image 5

How To Know What Item Is To Be Selected?

Since we satisfied the condition we know that weight w2 and w4 can be selected to maximize the total profit so our sequence becomes {0,1,0,1} where 0 denotes items which cannot be selected and 1 denotes item which can be selected.

Algorithm Used

Algorithm used can be seen below(image 6).

Image 6

Time Complexity Analysis

Time Complexity: O(N*W).
where ’N’ denotes the number of weight element and ‘W’ is the maximum capacity of our knapsack. As for every weight element we traverse through all weight capacities i.e., the loop will be iterated from 1<=w<=W, where “w ”is the weights of items.

Auxiliary Space: O(N*W).
The use of 2-D array of size ‘N*W’.