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 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 knapsack and the profit of items is maximum.
Generally, Knapsack problem have many practical applications. We have to face it at 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 item then we have to take 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 weight and profit. 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 airport and our knapsack(luggage) weight is 20 kg but according to airline rules we can carry max 15 kg weight then either we have to dropped items of 5 kg or have to pay extra charge of extra weight. If we don’t want to pay extra amount then we have to drop 5 kg weight items then we have to select those items in knapsack which are more important(costly).
Let the no. of items= n
Let the items are 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 following:
- Objective function
- Constraints
- Non-negative constraints
Types Of Knapsack Problem:
Knapsack problem is of two types given as following:
- 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. Thief cannot select the 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 break into fractions i.e. we can also select some portion of the item instead of selecting the whole item. Likewise, 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