The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
The most common problem being solved is the 0-1 knapsack problem, which restricts the number
of copies of each kind of item to zero or one. Given a set of items numbered from 1 up to , each with a weight and a value , along with a maximum weight capacity ,Maximize
subject to
and .Here
represents the number of instances of item to include in the knapsack. Informally, the problem is to maximize the sum of the values of the items in the knapsack so that the sum of the weights is less than or equal to the knapsack's capacity.The bounded knapsack problem (BKP) removes the restriction that there is only one of each item, but restricts the number
of copies of each kind of item to a maximum non-negative integer value :maximize
subject to
andThe unbounded knapsack problem (UKP) places no upper bound on the number of copies of each kind of item and can be formulated as above except for that the only restriction on
is that it is a non-negative integer.maximize
subject to
andOne example of the unbounded knapsack problem is given using the figure shown at the beginning of this article and the text "if any number of each box is available" in the caption of that figure.
The problem states-
“Which items should be placed in the knapsack so that the value or profit that is obtained by putting the items in the knapsack is maximum and the weight limit of the knapsack also does not exceed?”
In this article, we will discuss about 0/1 Knapsack Problem.
Read also : Fractional Knapsack Problem With Solution
In 0/1 Knapsack Problem,
Consider we are given-
T(i , j) = maximum value of the selected items if we can take items 1 to i and we have weight restrictions of j.
After filling the table completely, value of the last box represents the maximum possible value that be put in the knapsack.
To identify the items that must be put in the knapsack to obtain the maximum profit,
For the given set of items and knapsack capacity = 5 kg, find the optimal solution for the 0/1 knapsack problem making use of dynamic programming approach.
Item | Weight | Value |
1 | 2 | 3 |
2 | 3 | 4 |
3 | 4 | 5 |
4 | 5 | 6 |
OR
Find the optimal solution for the 0/1 knapsack problem making use of dynamic programming approach. Consider-
OR
A thief enters a house for robbing it. He can carry a maximal weight of 5 kg into his bag. There are 4 items in the house with the following weights and values. What items should thief take if he either takes the item completely or leaves it completely?
Item | Weight (kg) | Value ($) |
Mirror | 2 | 3 |
Silver nugget | 3 | 4 |
Painting | 4 | 5 |
Vase | 5 | 6 |
Here given that
Start filling the table row wise top to bottom from left to right using this following formula- T (i , j) = max { T ( i-1 , j ) , valuei + T( i-1 , j – weighti ) }
Finding T(1,1)
We have,
i = 1
j = 1
(value)i = (value)1 = 3
(weight)i = (weight)1 = 2
Substituting the values, we get-
T(1,1) = max { T(1-1 , 1) , 3 + T(1-1 , 1-2) }
T(1,1) = max { T(0,1) , 3 + T(0,-1) }
T(1,1) = T(0,1) { Ignore T(0,-1) }
T(1,1) = 0
Finding T(1,2)
We have,
i = 1
j = 2
(value)i = (value)1 = 3
(weight)i = (weight)1 = 2
Substituting the values, we get-
T(1,2) = max { T(1-1 , 2) , 3 + T(1-1 , 2-2) }
T(1,2) = max { T(0,2) , 3 + T(0,0) }
T(1,2) = max {0 , 3+0}
T(1,2) = 3
Finding T(1,3)
We have,
i = 1
j = 3
(value)i = (value)1 = 3
(weight)i = (weight)1 = 2
Substituting the values, we get-
T(1,3) = max { T(1-1 , 3) , 3 + T(1-1 , 3-2) }
T(1,3) = max { T(0,3) , 3 + T(0,1) }
T(1,3) = max {0 , 3+0}
T(1,3) = 3
Finding T(1,4)
We have,
i = 1
j = 4
(value)i = (value)1 = 3
(weight)i = (weight)1 = 2
Substituting the values, we get-
T(1,4) = max { T(1-1 , 4) , 3 + T(1-1 , 4-2) }
T(1,4) = max { T(0,4) , 3 + T(0,2) }
T(1,4) = max {0 , 3+0}
T(1,4) = 3
Finding T(1,5)
We have
i = 1
j = 5
(value)i = (value)1 = 3
(weight)i = (weight)1 = 2
Substituting the values, we get-
T(1,5) = max { T(1-1 , 5) , 3 + T(1-1 , 5-2) }
T(1,5) = max { T(0,5) , 3 + T(0,3) }
T(1,5) = max {0 , 3+0}
T(1,5) = 3
Finding T(2,1)
We have
i = 2
j = 1
(value)i = (value)2 = 4
(weight)i = (weight)2 = 3
Substituting the values, we get-
T(2,1) = max { T(2-1 , 1) , 4 + T(2-1 , 1-3) }
T(2,1) = max { T(1,1) , 4 + T(1,-2) }
T(2,1) = T(1,1) { Ignore T(1,-2) }
T(2,1) = 0
Finding T(2,2)
We have
i = 2
j = 2
(value)i = (value)2 = 4
(weight)i = (weight)2 = 3
Substituting the values, we get-
T(2,2) = max { T(2-1 , 2) , 4 + T(2-1 , 2-3) }
T(2,2) = max { T(1,2) , 4 + T(1,-1) }
T(2,2) = T(1,2) { Ignore T(1,-1) }
T(2,2) = 3
Finding T(2,3)
We have
i = 2
j = 3
(value)i = (value)2 = 4
(weight)i = (weight)2 = 3
Substituting the values, we get-
T(2,3) = max { T(2-1 , 3) , 4 + T(2-1 , 3-3) }
T(2,3) = max { T(1,3) , 4 + T(1,0) }
T(2,3) = max { 3 , 4+0 }
T(2,3) = 4
Finding T(2,4)
We have
We have,
i = 2
j = 4
(value)i = (value)2 = 4
(weight)i = (weight)2 = 3
Substituting the values, we get-
T(2,4) = max { T(2-1 , 4) , 4 + T(2-1 , 4-3) }
T(2,4) = max { T(1,4) , 4 + T(1,1) }
T(2,4) = max { 3 , 4+0 }
T(2,4) = 4
Finding T(2,5)
We have
i = 2
j = 5
(value)i = (value)2 = 4
(weight)i = (weight)2 = 3
Substituting the values, we get-
T(2,5) = max { T(2-1 , 5) , 4 + T(2-1 , 5-3) }
T(2,5) = max { T(1,5) , 4 + T(1,2) }
T(2,5) = max { 3 , 4+3 }
T(2,5) = 7
Similarly, after computing all the values and filling them in the table, we get-
Following this,
Item-1 and Item-2
That's it. Hope it will help you.
Hope it can help you!
#greedy-algorithm #0-1-knapsack