Introduction
Hello there, I hope you’re doing good. This blog is a detailed explanation of ‘what is knapsack problem’. Kindly, read the full blog to get your thoughts cleared on the topic.
Let’s get started…
What is Knapsack Problem:
Certainly, we have given a knapsack of the maximum capacity of m kg and n items with their weight and profit. Fill in the knapsack with a subset of items such that the selected weight is less than or equal to the capacity of the knapsack and the profit of items is maximum.
Generally, the Knapsack problem has many practical applications. We have to face it many times. This issue arises when we have a knapsack(bag/suitcase etc in which we can carry items) of specified maximum weight and have multiple items of different weights and costs(profits)and it is not possible to carry all of the items then we have to make a decision that which items be selected in knapsack so that profit be maximum and capacity constraint not break.
Example
(a) Suppose there is a thief who goes to a shop for robbery and he carries a knapsack(bag)of m kg. Moreover, the shop has multiple items with different weights and profits. The problem of the thief is to decide which item he should take so that knapsack is full and he gets the maximum value.
(b) Suppose we are at the airport and our knapsack(luggage) weight is 20 kg but according to airline rules we can carry a max 15 kg weight then either we have to drop items of 5 kg or have to pay an extra charge of extra weight. If we don’t want to pay an extra amount then we have to drop 5 kg weight items then we have to select those items in the knapsack which are more important(costly).
Let the no. of items= n
Let the items be i1, i2, … ,in.
Profit of these items are p1,p2, … ,pn respectively and
weight are w1,w2, … ,wn respectively
Basically, it can be mathematically represented by using Linear Programming Problem(LPP). LPP has three segments which are given as follows:
- Objective function
- Constraints
- Non-negative constraints
Types Of Knapsack Problem:
The knapsack problem is of two types given as follows:
- 0/1 Knapsack problem
- Fractional Knapsack problem
0/1 Knapsack Problem:- In this either the whole item can be selected(1) or not selected at all(0) i.e. we can select a portion of any item according to the need. A thief cannot select some portion of any item as and when needed.
It can be represented in the following form:
Max z=∑pi*xi
S.t.∑wi ≤ m
And xi=1 or 0
Where, p=profit
w=weight
x=solution or selection value
m=capacity
Fractional knapsack problem:– In this problem, the item can be broken into fractions i.e. we can also select some portion of the item instead of selecting the whole item. Likewise, the whole item can be selected (1) or may not be selected at all (0), or some portion of it can be selected (between 0 to 1).
We can represent this problem using LPP in the following form:
Max z =∑pi*xi
S.t. =∑wi*xi≤m
And 0 ≤ xi ≤ 1
Blog by: Mr. Rahul Agarwal
Department of Information & Technology
Biyani Group of Colleges, Jaipur
Thank you for reading our blog. Kindly, share it
