Knapsack Problem using Dynamic Programming
In this article, we will discuss how to solve Knapsack Problem using Dynamic Programming. We have already discussed how to solve knapsack problem using greedy approach.
Knapsack Problem using Dynamic Programming
- Problem : Given a set of items, each having different weight and value or profit associated with it. Find the set of items such that the total weight is less than or equal to a capacity of the knapsack and the total value earned is as large as possible.
- The knapsack problem is useful in solving resource allocation problem. Let X = < x1, x2, x3, . . . . . , xn> be the set of n items. Sets W = <w1, w2, w3, . . . , wn> and V = < v1, v2, v3, . . . , vn> are weight and value associated with each item in X. Knapsack capacity is M unit.
- The knapsack problem is to find the set of items which maximizes the profit such that collective weight of selected items does not cross the knapsack capacity.
- Select items from X and fill the knapsack such that it would maximize the profit. Knapsack problem has two variations. 0/1 knapsack, that does not allow breaking of items. Either add an entire item or reject it. It is also known as a binary knapsack. Fractional knapsack allows breaking of items. Profit will be earned proportionally.
Mathematical formulation
We can select any item only ones. We can put items xi in knapsack if knapsack can accommodate it. If the item is added to a knapsack, the associated profit is accumulated.
Knapsack problem can be formulated as follow :
Maximize \[ sum_{i=1}^{n} v_i x_i \] subjected to \[ sum_{i=1}^{n} w_i x_i le M \]
\[ x_i in (0, 1) \] for binary knapsack
\[ x_i in [0, 1] \] for fractional knapsack
We will discuss two approaches for solving knapsack using dynamic programming.
First Approach for Knapsack Problem using Dynamic Programming
If the weight of the item is larger than the remaining knapsack capacity, we skip the item, and the solution of the previous step remains as it is. Otherwise, we should add the item to the solution set and the problem size will be reduced by the weight of that item. Corresponding profit will be added for the selected item.
Dynamic programming divides the problem into small sub-problems. Let V is an array of the solution of sub-problems. V[i, j] represents the solution for problem size j with first i items. The mathematical notion of the knapsack problem is given as :
V [1 …. n, 0 … M] : Size of the table
V (n, M) = Solution
n = Number of items
Algorithm
Algorithm for binary knapsack using dynamic programming is described below :
Algorithm DP_BINARY_KNAPSACK (V, W, M)
// Description: Solve binary knapsack problem using dynamic programming
// Input: Set of items X, set of weight W, profit of items V and knapsack capacity M
// Output: Array V, which holds the solution of problem
for i ← 1 to n do
V[i, 0] ← 0
end
for i ← 1 to M do
V[0, i] ← 0
end
for V[0, i] ← 0 do
for j ← 0 to M do
if w[i] ≤ j then
V[i, j] ← max{V[i-1, j], v[i] + V[i – 1, j – w[i]]}
else
V[i, j] ← V[i – 1, j] // w[i]>j
end
end
end
The above algorithm will just tell us the maximum value we can earn with dynamic programming. It does not speak anything about which items should be selected. We can find the items that give optimum result using the following algorithm
Algorithm TRACE_KNAPSACK(w, v, M)
// w is array of weight of n items
// v is array of value of n items
// M is the knapsack capacity
SW ← { }
SP ← { }
i ← n
j ← M
while ( j> 0 ) do
if (V[i, j] == V[i – 1, j]) then
i ← i – 1
else
V[i, j] ← V[i, j] – vi
j ← j – w[i]
SW ← SW +w[i]
SP ← SP +v[i]
end
end
Complexity analysis
With n items, there exist 2n subsets, the brute force approach examines all subsets to find the optimal solution. Hence, the running time of the brute force approach is O(2n). This is unacceptable for large n.
Dynamic programming finds an optimal solution by constructing a table of size n ´ M, where n is a number of items and M is the capacity of the knapsack. This table can be filled up in O(nM) time, same is the space complexity.
- Running time of Brute force approach is O(2n).
- Running time using dynamic programming with memorization is O(n * M).
Example
Example: Find an optimal solution for following 0/1 Knapsack problem using dynamic programming: Number of objects n = 4, Knapsack Capacity M = 5, Weights (W1, W2, W3, W4) = (2, 3, 4, 5) and profits (P1, P2, P3, P4) = (3, 4, 5, 6).
Solution:
Solution of the knapsack problem is defined as,
We have the following stats about the problem,
Item | Weight (wi) | Value (vi) |
I1 | 2 | 3 |
I2 | 3 | 4 |
I3 | 4 | 5 |
I4 | 5 | 6 |
- Boundary conditions would be V [0, i] = V[i, 0] = 0. Initial configuration of table looks like.
j → | ||||||||
Item Detail | 0 | 1 | 2 | 3 | 4 | 5 | ||
i=0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
i=1 | w1=2 | v1=3 | 0 | |||||
i=2 | w2=3 | v2=4 | 0 | |||||
i=3 | w3=4 | v3=5 | 0 | |||||
i=4 | w4=5 | v4=6 | 0 |
Filling first column, j = 1
V [1, 1] ⇒ i = 1, j = 1, wi = w1 = 2
As, j < wi, V [i, j] = V [i – 1, j]
V [1, 1] = V [0, 1] = 0
V [2, 1] ⇒ i = 2, j = 1, wi = w2 = 3
As, j < wi, V [i, j] = V [i – 1, j]
V [2, 1] = V [1, 1] = 0
V [3, 1] ⇒ i = 3, j = 1, wi = w3 = 4
As, j < wi, V [i, j] = V [i – 1, j]
V [3, 1] = V [2, 1] = 0
V [4, 1] ⇒ i = 4, j = 1, wi = w4 = 5
As, j < wi, V[i, j] = V[i – 1, j]
V [4, 1] = V [3, 1] = 0
Filling first column, j = 2
V[1, 2] ⇒ i = 1, j = 2, wi = w1 = 2, vi = 3
As, j ≥ wi, V [i, j]=max {V [i – 1, j], vi + V[i – 1, j – wi] }
= max {V [0, 2], 3 + V [0, 0]}
V[1, 2] = max (0, 3) = 3
V[2, 2] ⇒ i = 2, j = 2, wi = w2 = 3, vi = 4
As, j < wi, V [i, j] = V[i – 1, j]
V[2, 2] = V[1, 2] = 3
V[3, 2] ⇒ i = 3, j = 2, wi = w3 = 4, vi = 5
As, j < wi, V[i, j] = V[i – 1, j]
V[3, 2] = V [2, 2] = 3
V[4, 2] ⇒ i = 4, j = 2, wi = w4 = 5, vi = 6
As, j < wi, V[i, j] = V[i – 1, j]
V[4, 2] = V[3, 2] = 3
Filling first column, j = 3
V[1, 3] ⇒ i = 1, j = 3, wi = w1 = 2, vi = 3
As, j ≥ wi, V [i, j]=max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [0, 3], 3 + V [0, 1]}
V[1, 3] = max (0, 3) = 3
V[2, 3] ⇒ i = 2, j = 3, wi = w2 = 3, vi = 4
As, j ≥ wi, V [i, j] = max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [1, 3], 4 + V [1, 0]}
V[2, 3] = max (3, 4) = 4
V[3, 3] ⇒ i = 3, j = 3, wi = w3 = 4, vi = 5
As, j < wi, V [i, j] = V [i – 1, j]
V[3, 3] = V [2, 3] = 4
V[4, 3] ⇒ i = 4, j = 3, wi = w4 = 5, vi = 6
As, j < wi, V[i, j] = V[i – 1, j]
V[4, 3] = V [3, 3] = 4
Filling first column, j = 4
V[1, 4] ⇒ i = 1, j = 4, wi = w1 = 2, vi = 3
As, j ≥ wi, V [i, j]=max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [0, 4], 3 + V [0, 2]}
V[1, 4] = max (0, 3) = 3
V[2, 4] ⇒ i = 2, j = 4, wi = w2 = 3 , vi = 4
As, j ≥ wi, V [i, j] =max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [1, 4], 4 + V [1, 1]}
V[2, 4] = max (3, 4 + 0) = 4
V[3, 4] ⇒ i = 3, j = 4, wi = w3 = 4, vi = 5
As, j ≥ wi, V [i, j]=max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [2, 4], 5 + V [2, 0]}
V[3, 4] = max (4, 5 + 0) = 5
V[4, 4] ⇒ i = 4, j = 4, wi = w4 = 5, vi = 6
As, j < wi, V [i, j] = V [i – 1, j]
V[4, 4] = V [3, 4] = 5
Filling first column, j = 5
V [1, 5] ⇒ i = 1, j = 5, wi = w1 = 2, vi = 3
As, j ≥ wi, V [i, j] = max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [0, 5], 3 + V [0, 3]}
V[1, 5] = max (0, 3) = 3
V[2, 5] ⇒ i = 2, j = 5, wi = w2 = 3, vi = 4
As, j ≥ wi, V [i, j] =max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [1, 5], 4 + V [1, 2]}
V[2, 5] = max (3, 4 + 3) = 7
V[3, 5] ⇒ i = 3, j = 5, wi = w3 = 4, vi = 5
As, j ≥ wi, V [i, j] = max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [2, 5], 5 + V [2, 1]}
V[3, 5] = max (7, 5 + 0) = 7
V [4, 5] ⇒ i = 4, j = 5, wi = w4 =5, vi = 6
As, j ≥ wi, V [i, j] = max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [3, 5], 6 + V [3, 0]}
V[4, 5] = max (7, 6 + 0) = 7
Final table would be,
j→ | ||||||||
Item Detail | 0 | 1 | 2 | 3 | 4 | 5 | ||
i=0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
i=1 | w1=2 | v1=3 | 0 | 0 | 3 | 3 | 3 | 3 |
i=2 | w2=3 | v2=4 | 0 | 0 | 3 | 4 | 4 | 7 |
i=3 | w3=4 | v3=5 | 0 | 0 | 3 | 4 | 5 | 7 |
i=4 | w4=5 | v4=6 | 0 | 0 | 3 | 4 | 5 | 7 |
Find selected items for M = 5
Step 1 : Initially, i = n = 4, j = M = 5
V[i, j] = V[4, 5] = 7
V[i – 1, j] = V[3, 5] = 7
V[i, j] = V[i – 1, j], so don’t select ith item and check for the previous item.
so i = i – 1 = 4 – 1 = 3
Solution Set S = { }
Step 2 : i = 3, j = 5
V[i, j] = V[3, 5] = 7
V[i – 1, j] = V[2, 5] = 7
V[i, j] = V[i – 1, j], so don’t select ith item and check for the previous item.
so i = i – 1 = 3 – 1 = 2
Solution Set S = { }
Step 3 : i = 2, j = 5
V[i, j] = V[2, 5] = 7
V[i – 1, j] = V[1, 5] = 3
V[i, j] ≠ V[i – 1, j], so add item Ii = I2 in solution set.
Reduce problem size j by wi
j = j – wi = j – w2 = 5 – 3 = 2
i = i – 1 = 2 – 1 = 1
Solution Set S = {I2}
Step 4 : i = 1, j = 2
V[1, j] = V[1, 2] = 3
V[i – 1, j] = V[0, 2] = 0
V[i, j] ≠ V[i – 1, j], so add item Ii = I1 in solution set.
Reduce problem size j by wi
j = j – wi = j – w1 = 2 – 2 = 0
Solution Set S = {I1, I2}
Problem size has reached to 0, so final solution is
S = {I1, I2} Earned profit = P1 + P2 = 7
Second Approach: Set Method for Knapsack Problem using Dynamic Programming
- The first approach is suitable when knapsack capacity is small. With large knapsack, the first approach is not advisable from computation as well as memory requirement point of view.
- The secondapproach discussed below is more suitable when problem instance is large.
- In forward approach, dynamic programming solves knapsack problem as follow:
1. Set S0 = {(0, 0)}
2. S1i = {(p, w) | (p – pi) ∈ Si, (w – wi) ∈ Si }
We can obtain Si + 1 by invoking xi + 1
- If xi = 0 (item xi is excluded) then S1i = Si
- If xi = 1 (item xi is included) then S1i is computed by adding (pi + 1, wi + 1) in each state of Si.
1. S i + 1 = MERGE_PURGE(Si, S1i). MERGE_PURGE does following:
For two pairs (px, wx) ∈ Si + 1 and (py, wy) ∈ Si + 1, if px ≤ py and wx ≥ wy, we say that (px, wx) is dominated by (py, wy). And the pair (px, wx) is discarded.
It also purges all the pairs (p, w) from Si + 1 if w > M, i.e. it weight exceeds knapsack capacity.
2. Repeat step 1 n times
3. fn(M) = Sn. This will find the solution of KNAPSACK(1, n, M).
4. for each pair (p, w) ∈ Sn
if (p, w) ∈ Sn – 1, then set xn = 0
if (p, w) ∉ Sn – 1, then set xn = 1, update p = p – xn and w = w – wn
Algorithm
Algorithm
DP_KNAPSACK(X, P, W, M)
// Description: Solve knapsack problem using dynamic programming
// Input: Set of items X, profit P, weight W and knapsack capacity M
// Output: Vector x indicating selection/rejection of items.
S
0
= { (0, 0) }
for
i ← 0 to n – 1
do
S
i
1
← {(p, w) | for each (x, y) ∈ Si, p = x + p
i+1
, w = y + w
i+1
}
S
1
i+1
← MERGE_PURGE(S
i
,S
1
i
)
end
for
i ← n to 1
do
Select last pair (p
x
, w
x
) ∈ S
n
if
(p
x
, w
x
) ∈ S
n–1
then
x
i
← 0
else
x
i
← 1
end
end
Examples
Example: Solve the instance of 0/1 knapsack problem using dynamic Programming : n = 4, M = 25, (P1, P2, P3 P4) = (10, 12, 14, 16), (W1, W2, W3, W4) = (9, 8, 12, 14)
Solution:
Knapsack capacity is very large, i.e. 25, so tabular approach won’t be suitable. We will use the set method to solve this problem
Initially, S0 = { (0, 0) }
Iteration 1:
Obtain S10 by adding pair (p1, w1) = (10, 9) to each pair of S0
S10 = S0 + (10, 9) = {(10, 9)}
Obtain S1 by merging and purging S0 and S10
S1 = MERGE_PURGE (S0, S10)
= { (0, 0), (10, 9) }
Iteration 2:
Obtain S11 by adding pair (p2, w2) = (12, 8) to each pair of S1
S11 = S1 + (12, 8) = {(12, 8), (22, 17)}
Obtain S2 by merging and purging S1 and S11
S2 = MERGE_PURGE(S1, S11)
= { (0, 0), (12, 8), (22, 17) }
Pair (10, 9) is discarded because pair (12, 8) dominates (10, 9)
Iteration 3:
Obtain S12 by adding pair (p3, w3) = (14, 12) to each pair of S2
S12 = S2 + (14, 12)
= { (14, 12), (26, 20), (36, 29) }
Obtain S3 by merging and purging S2 and S12 .
S3 = MERGE_PURGE (S2, S12 )
= { (0, 0), (12, 8), (22, 17), (14, 12), (26, 20) }
Pair (36, 29) is discarded because its w > M
Iteration 4:
Obtain S13 by adding pair (p4, w4) = (16, 14) to each pair of S3
S13 = S3 + (16, 14)
= { (16, 14), (28, 22), (38, 31), (30, 26), (42, 34) }
Obtain S4 by merging and purging S3 and S13.
S4 = MERGE_PURGE (S3, S13)
= { (0, 0), (12, 8), (14, 12), (16, 14), (22, 17), (26, 20), (28, 22) }
Pair (38, 31), (30, 26) ,and (42, 34) are discarded because its w > M
Find optimal solution
Here, n = 4.
Start with the last pair in S4, i.e. (28, 22)
(28, 22) ∈ S4 but (28, 22) ∉ S3
So set xn = x4 = 1
Update,
p = p – p4 = 28 – 16 = 12
w = w – w4 = 22 – 14 = 8
n = n – 1 = 4 – 1 = 3
Now n = 3, pair (12, 8) ∈ S3 and (12, 8) ∈ S2
So set xn = x3 = 0
n = n – 1 = 3 – 1 = 2
Now n = 2, pair(12, 8) ∈ S2 but (12, 8) ∉ S1
So set xn = x2 = 1
Update,
p = p – p2 = 12 – 12 = 0
w = w – w2 = 8 – 8 = 0
Problem size is 0, so stop.
Optimal solution vector is (x1, x2, x3, x3) = (0, 1, 0, 1) Thus, this approach selects pair (12, 8) and (16, 14) which gives profit of 28.
Example: Generate the sets Si, 0 ≤ i ≤ 3 for following knapsack instance. N = 3, (w1, w2, w3) = (2, 3, 4) and (p1, p2, p3) = (1, 2, 5) with M = 6. Find optimal solution.
Solution:
Initially, S0 = {(0, 0) }
Iteration 1:
Obtain S10 by adding pair (p1, w1) = (1, 2) to each pair of S0
S10 = S0 + (1, 2) = {(1, 2)}
Obtain S1 by merging and purging S0 and S10
S1 = MERGE_PURGE (S0, S10)
= { (0, 0), (1, 2) }
Iteration 2:
Obtain S11 by adding pair (p2, w2) = (2, 3) to each pair of S1
S11 = S1 + (2, 3) = {(2, 3), (3, 5)}
Obtain S2 by merging and purging S1 and S11
S2 = MERGE_PURGE(S1, S11)
= { (0, 0), (1, 2), (2, 3), (3, 5) }
Iteration 3:
Obtain S12 by adding pair (p3, w3) = (5, 4) to each pair of S2
S12 = S2 + (5, 4) = {(5, 4), (6, 6), (7, 7), (8, 9) }
Obtain S3 by merging and purging S2 and S12 .
S3 = MERGE_PURGE (S2, S12)
= { (0, 0), (1, 2), (2, 3), (5, 4), (6, 6) }
Pair (7, 7) and (8, 9) are discarded because their w > M
Pair (3, 5) is discarded because pair (5, 4) dominates (3, 5)
Find optimal solution:
Here, n = 3.
Start with the last pair in S3, i.e. (6, 6)
(6, 6) ∈ S3 but (6, 6) ∉ S2
So set xn = x3 = 1
Update,
p = p – p3 = 6 – 5 = 1
w = w – w3 = 6 – 4 = 2
Now n = 2, pair(1, 2) ∈ S2 and (1, 2) ∈ S1
So set xn = x2 = 0
Now n = 1, pair(1, 2) ∈ S1 but (1, 2) ∉ S0
So set xn = x1 = 1
Optimal solution vector is (x1, x2, x3) = (1, 0, 1)
Thus, this approach selects pair (1, 2) and (5, 4)
Some Popular Problems Solved using Dynamic Programming
- Binomial Coefficient
- Making a Change
- Knapsack Problem
- Multistate Graph Problem
- Optimal Binary Search Tree
- Matrix Chain Multiplication
- Longest Common Subsequence
- Bellman-Ford (Single Source Shortest Path) Algorithm
- Floyd-Warshall (All Pair Shortest Path) Problem
- Assembly Line Scheduling
- Travelling Salseman Problem
- Flow Shop Scheduling
Additional Reading: Implementation of Knapsack Problem using Dynamic Programming
Please recheck the tracing knapsack algorithm
this V[i, j] ← V[i, j] – vi will be V[i, j] ← V[i, j] – v[i]
or not?
Please reply ASAP.
It would be V[i, j] – vi. vi is the profit of an individual item, whereas V[i, j] is the particular cell of the table, there is nothing like v[i]