Knapsack Problem explained

The knapsack problem is one of the oldest problems that has been in the study for a century and the earliest reference to this problem dates back to 1897. The earliest knapsack problem can be found in the work of the mathematicians named Tobias Dantzig, this problem is referred for the packing of the most valuable items without overloading the luggage to be carried. The knapsack problem is one of the famous algorithms of dynamic programming and this problem falls under the optimization category.

Also, the knapsack problem is a combinatorial optimization problem, in which the items are provided with a weight and a value, and with the metric provided, we have determined the combination of the items to be chosen from the knapsack when we are given a maximum weight limit.

Also, the knapsack problem is a resource allocation problem and is used in real-life scenarios where we have to divide the available resources under a fixed budget or in a given time constraint. In the real world, we can see this algorithm working, like in finance and investment for selection of investment and portfolio or finding the way for cutting the raw material such that the least waste occurs.

The knapsack problem has been the third most popular algorithm problem in the nineteenth century.


Dynamic programming

A dynamic problem is a kind of divide and conquers the problem in which the problem is solved by solving the subproblems that have arisen due to the division of the main problem. The subproblem is further simplified into more subproblems and this loop keeps on going until we have reached the division where the subproblem either cannot be simplified further or the solution for the subproblem is at the simplest level.

The main objective of dynamic programming is to store the solution of the subproblem in form of a table such as an array or matrix and when again the similar format of the subproblem is encountered then we can simply apply the solution that already exists in the table which was previously solved for us.


So the particular steps that come in the solution of the dynamic programming problem are:

  1. Making an iterative loop to reach the simplest subproblem and then finding the solution to that subproblem
  2. Formulate some rule that is common in the solution of the subproblem and that can be applied in solving another subproblem also
  3. Store this solution in a table and this table can be further used for formulating the rules for the solution
  4. And finally, you will have a solution to your original subproblem when you have solved all the subproblems.


Knapsack Problem

Let’s assume that you might have woken up on a mysterious island and many precious artifacts are collectibles. Each artifact has a different worth and weight. You have a bag in which you can put your collected artifacts but this bag has one limitation about the weight that you can put inside the bag. So, now you have to think that which are the artifacts that you have to put inside your bag such that you can put the artifacts with the maximum worth and at the same time you can do it in the limitation that is provided for the maximum weight it can carry.

These kinds of problems are known as the knapsack problem. Also along with this, there are many further types of knapsack problem such as

0-1 knapsack problem, in this type of problem you have only one item for each kind so either you can choose to take it or leave it.

Bounded Knapsack problem, in such a problem there is an upper bound to the number of items in each kind, each kind has more than one item but cannot be infinite therefore they will tend to have an upper bound to them.

Unbounded Knapsack Problem, as the bounded knapsack problem has the boundary this knapsack problem is not bounded and in that case, every kind can have as much item it wants.

Fractional Knapsack Problem, here the items can even exist in a fraction form, in the real example the powdered gold exists as the fraction and this problem suits the need in solving the real-life requirement.

The knapsack problem falls in the category of NP-complete, thus in this case no known algorithm is both fast as well as correct.



2 thoughts on “Knapsack Problem explained

  • October 18, 2020 at 5:30 am

    can u explain branch and bound with tcp plz


Leave a Reply

Your email address will not be published. Required fields are marked *