Knapsack Problem
Introduction: -
The rucksack problem or knapsack problem is usually problem found in combinatorial optimization: For example — Given a set of items, each with a certain weight and a particular value, made to determine the number of each and every item to include in a certain collection, so that the total weight is very less than or equal to a given amount and the total value can be as large as possible. It derives its name from when someone has faced a problem and someone who is constrained by a given amount of size of knapsack and it must fill it with the most valuable (expensive) items.
The problem often arises when the resource allocation has the financial constraints and is usually studied in fields such as complexity theory, computer science, applied mathematics, combinatorics, cryptography, and daily fantasy sports.
History: -
“As we know that the knapsack problem has already been studied for around or even more than a century now, with early works dating as far back as 1897. Even the name of “knapsack problem” dates really back to the famous mathematician Tobias Dantzig (1884–1956) and it usually refers to the commonplace problem of packing the most valuable (expensive) and useful items without ever overloading the luggage.”
We will solve this problem using recursion:
Calculating The Time Complexity: -
if we look very carefully, we will be deprogramming the similar overlapping problem one after the other. Hence, the time complexity of the code given above will be exponential which means i.e., 2^n
Now, how can we improve the above given solution of the problem?
Yes, we can improve the above given results by using Dynamic Programming, and it is to be noted that we have to remember the results obtained in the previous problem.
Time complexity of the above given problem will always be O(nW), where the n is and will be the number of items and W will be the capacity of the knapsack given.
Mathematical Expression
Let us take into consideration that a problem has the following weights and profits:
Weight — {3, 4, 5, 6} Profit — {2, 3, 4, 1}
Total number of items are 4 and the weight of the knapsack is 8kg.
Now to solve this problem, firstly we need to create a matrix, where the column represents the weight which is 8. The profit and weight of the item is represented by the rows. The problem is divided into sub-problems that is 0, 1, 2, 3, 4, 5, 6, 7, 8.
In the cells we save the solution of the sub problems and in the final cell the answer of the problem would be saved and stored. The weights and their profits are mentioned in ascending order.
w= {3, 4, 5, 6} v= {2, 3, 4, 1}
Since there’s no item for w=0, the values saved in the first row and column would be 0 as well.
1. While i=1, w=5
The weight of the knapsack is 5, the only item has the weight is 3. The value to be saved is 2 to the weight 3 in the matrix {1, 5}. Therefore, we filled the item with the weight of 3kg.
Similarly, when i=1, w=6; i=1, w=7; i=1, w=8; We’ve placed the profit and the weight corresponding to each other in the matrix {1, 6}, {1, 7}, {1, 8}.
2. While i=2, w=7
The weight of the knapsack is 7 and we have two items with the weight 3 and 4 to be saved in the matrix from our set. Items with the weight 4 and 3 can be placed in the knapsack and the profits of the respective weights are 2, 3. Hence the final profit is 5. Therefore, we have saved the value as 5 in the matrix {2, 7} and similarly in the matrix of {2, 8}.
3. While i=2, w=3
The weight of knapsack is 3 and we have two values in the set to be saved with the weight 3 and 4. Therefore, we have saved the value 2 in the matrix as we have placed the item of th weight 3 in the matrix {2, 3}.
4. While i=4, w=6
Max weight of the subproblem is 6 and all the items (3,2) (4,3) (5,4) (6,1) can be chosen so we can choose the third item or fourth item and the cell will be filled with the value of the third item that is 4 as the value of the third item is more than the value of the fourth item.
Time complexity: O(nW)
Thank You For Reading My Blog
