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 :

Knapsack Problem using Dynamic Programming

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 i ← 1 to n 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,

ItemWeight (wi)Value (vi)
I123
I234
I345
I456
  • Boundary conditions would be V [0, i] = V[i, 0] = 0. Initial configuration of table looks like.
j →
 Item Detail012345
i=0  000000
i=1w1=2v1=30     
i=2w2=3v2=40     
i=3w3=4v3=50     
i=4w4=5v4=60     

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 = w=  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 = w=  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 = w=  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 = w=  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 = w=  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 = w=  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 = w=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 012345
i=0  000000
i=1w1=2v1=3003333
i=2w2=3v2=4003447
i=3w3=4v3=5003457
i=4w4=5v4=6003457

Find selected items for M = 5

Step 1 : Initially, i = n = 4, j = M = 5

Knapsack Problem using Dynamic Programming example

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

example of Knapsack Problem using Dynamic Programming

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

knapsack problem

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.

S0= { (0, 0) }
for i ← 0 to n – 1 do
  Si1 ← {(p, w) | for each (x, y) ∈ Si, p = x + pi+1, w = y + wi+1 }
  S1i+1 ← MERGE_PURGE(Si,S1i )
end

for i ← n to 1 do
  Select last pair (px, wx) ∈ Sn
  if (px, wx) ∈ Sn–1 then
    xi ← 0
  else
    xi ← 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 S

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)


Additional Reading: Implementation of Knapsack Problem using Dynamic Programming