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 = < x₁, x₂, x₃, . . . . . , x_n> be the set of n items. Sets W = <w₁, w₂, w₃, . . . , w_n> and V = < v₁, v₂, v₃, . . . , v_n> 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 x_i 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 2ⁿ subsets, the brute force approach examines all subsets to find the optimal solution. Hence, the running time of the brute force approach is O(2ⁿ). 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(2ⁿ).
• 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 (W₁, W₂, W₃, W₄) = (2, 3, 4, 5) and profits (P₁, P₂, P₃, P₄) = (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, w_i = w₁ = 2

As, j < w_i, V [i, j] = V [i – 1, j]

V [1, 1] = V [0, 1] = 0

V [2, 1] ⇒ i = 2, j = 1, w_i = w₂  =  3

As, j < w_i, V [i, j] = V [i – 1, j]

V [2, 1] = V [1, 1] = 0

V [3, 1] ⇒ i = 3, j = 1, w_i = w₃  =  4

As, j < w_i,  V [i, j] = V [i – 1, j]

V [3, 1] = V [2, 1] = 0

V [4, 1] ⇒ i = 4, j = 1,  w_i = w₄  =  5

As, j < w_i, 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, w_i = w₁  =  2, v_i = 3

As, j ≥ w_i, V [i, j]=max {V [i – 1, j], v_i + V[i – 1, j – w_i] }

= max {V [0, 2], 3 + V [0, 0]}

V[1, 2] = max (0, 3) = 3

V[2, 2] ⇒ i = 2, j = 2, w_i = w₂  =  3, v_i = 4

As, j < w_i, V [i, j] = V[i – 1, j]

V[2, 2] = V[1, 2] = 3

V[3, 2] ⇒ i = 3, j = 2, w_i = w₃  =  4, v_i = 5

As, j < w_i, V[i, j] = V[i – 1, j]

V[3, 2] = V [2, 2] = 3

V[4, 2] ⇒ i = 4, j = 2, w_i = w₄ = 5, v_i = 6

As, j < w_i, 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, w_i = w₁ = 2, v_i = 3

As, j ≥ w_i, V [i, j]=max {V [i – 1, j], v_i + V [i – 1, j – w_i] }

= max {V [0, 3], 3 + V [0, 1]}

V[1, 3] = max (0, 3) = 3

V[2, 3] ⇒ i = 2, j = 3, w_i = w₂ = 3, v_i = 4

As, j ≥ w_i, V [i, j] = max {V [i – 1, j], v_i + V [i – 1, j – w_i] }

= max {V [1, 3], 4 + V [1, 0]}

V[2, 3] = max (3, 4) = 4

V[3, 3] ⇒ i = 3, j = 3, w_i = w₃ = 4, v_i = 5

As, j < w_i, V [i, j] = V [i – 1, j]

V[3, 3] = V [2, 3] = 4

V[4, 3] ⇒ i = 4, j = 3, w_i = w₄ = 5, v_i = 6

As, j < w_i, 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,  w_i = w₁ = 2, v_i = 3

As, j ≥ w_i,  V [i, j]=max {V [i – 1, j], v_i + V [i – 1, j – w_i] }

= max {V [0, 4], 3 + V [0, 2]}

V[1, 4] = max (0, 3) = 3

V[2, 4] ⇒ i = 2, j = 4,  w_i = w₂ = 3 , v_i = 4

As, j ≥ w_i,  V [i, j] =max {V [i – 1, j], v_i + V [i – 1, j – w_i] }

= max {V [1, 4], 4 + V [1, 1]}

V[2, 4] = max (3, 4 + 0)  = 4

V[3, 4]  ⇒  i = 3, j = 4,  w_i = w₃ = 4, v_i = 5

As, j ≥ w_i,  V [i, j]=max {V [i – 1, j], v_i + V [i – 1, j – w_i] }

= max {V [2, 4], 5 + V [2, 0]}

V[3, 4] = max (4, 5 + 0) = 5

V[4, 4] ⇒ i = 4, j = 4, w_i = w₄ = 5, v_i = 6

As, j < w_i, 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, w_i = w₁ = 2, v_i = 3

As, j ≥ w_i,  V [i, j] = max {V [i – 1, j], v_i + V [i – 1, j – w_i] }

= max {V [0, 5], 3 + V [0, 3]}

V[1, 5] = max (0, 3) = 3

V[2, 5] ⇒ i = 2, j = 5, w_i = w₂ = 3, v_i = 4

As, j ≥ w_i,  V [i, j] =max {V [i – 1, j], v_i + V [i – 1, j – w_i] }

= max {V [1, 5], 4 + V [1, 2]}

V[2, 5] = max (3, 4 + 3) = 7

V[3, 5] ⇒ i = 3, j = 5,  w_i = w₃ = 4, v_i = 5

As, j ≥ w_i, V [i, j] = max {V [i – 1, j], v_i + V [i – 1, j – w_i] }

= max {V [2, 5], 5 + V [2, 1]}

V[3, 5] = max (7, 5 + 0) = 7

V [4, 5]  ⇒  i = 4,   j = 5,  w_i = w₄  =5, v_i = 6

As, j ≥ w_i,  V [i, j] = max {V [i – 1, j], v_i + V [i – 1, j – w_i] }

= 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 i^th 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 i^th 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 = I₂ in solution set.

Reduce problem size j by w_i

j = j – w_i = j – w₂ = 5 – 3 = 2

i = i – 1 = 2 – 1 = 1

Solution Set S = {I₂}

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 = I₁ in solution set.

Reduce problem size j by w_i

j = j – w_i = j – w₁ = 2 – 2 = 0

Solution Set S = {I₁, I₂}

Problem size has reached to 0, so final solution is
S = {I₁, I₂} Earned profit = P₁ + P₂ = 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 S⁰ = {(0, 0)}

2.     S₁ⁱ = {(p, w) | (p – p_i) ∈ Sⁱ, (w – w_i) ∈ Sⁱ }

We can obtain S^{i + 1} by invoking x_{i + 1}

• If x_i = 0 (item x_i is excluded) then S₁ⁱ = Sⁱ
• If x_i = 1 (item x_i is included) then S₁ⁱ is computed by adding (p_{i + 1}, w_{i + 1}) in each state of Sⁱ.

1.     S ^{i + 1} = MERGE_PURGE(Sⁱ, S₁ⁱ).  MERGE_PURGE does following:

         For two pairs (p_x, w_x) ∈ S^{i + 1} and (p_y, w_y) ∈ S^{i + 1}, if p_x ≤ p_y and w_x ≥ w_y, we say that (p_x, w_x) is dominated by (p_y, w_y). And the pair (p_x, w_x) is discarded.

         It also purges all the pairs (p, w) from S^{i + 1} if w > M, i.e. it weight exceeds knapsack capacity.

2.     Repeat step 1 n times

3.     f_n(M) = Sⁿ. This will find the solution of KNAPSACK(1, n, M).

4.     for each pair (p, w) ∈ Sⁿ

if (p, w) ∈ S^{n – 1}, then set x_n = 0

if (p, w) ∉ S^{n – 1}, then set x_n = 1, update p = p – x_n and w = w – w_n

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) }

for

i ← 0 to n – 1 

do

  S

_i

¹

 ← {(p, w) | for each (x, y) ∈ Si, p = x + p

_i+1

, w = y + w

_i+1

 }
  S

₁

ⁱ⁺¹

 ← MERGE_PURGE(S

ⁱ

,S

₁

ⁱ

 )

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, (P₁, P₂, P₃ P₄) = (10, 12, 14, 16), (W₁, W₂, W₃, W₄) = (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, S⁰ = { (0, 0) }

Iteration 1:

Obtain S₁⁰ by adding pair (p₁, w₁) = (10, 9) to each pair of S⁰

S₁⁰ = S⁰ + (10, 9) = {(10, 9)}

Obtain S¹ by merging and purging S⁰ and S₁⁰

S¹ = MERGE_PURGE (S⁰, S₁⁰)

= { (0, 0), (10, 9) }

Iteration 2:

Obtain S₁¹  by adding pair (p₂, w₂) = (12, 8) to each pair of S¹

S₁¹ = S¹ + (12, 8) = {(12, 8), (22, 17)}

Obtain S² by merging and purging S¹ and S₁¹

S² = MERGE_PURGE(S¹, S₁¹)

= { (0, 0), (12, 8), (22, 17) }

Pair (10, 9) is discarded because pair (12, 8) dominates (10, 9)

Iteration 3:

Obtain S₁² by adding pair (p₃, w₃) = (14, 12) to each pair of S²

S₁² = S² + (14, 12)

= { (14, 12), (26, 20), (36, 29) }

Obtain S³ by merging and purging S² and S₁² .

S³ = MERGE_PURGE (S², S₁² )

= { (0, 0), (12, 8), (22, 17), (14, 12), (26, 20) }

Pair (36, 29) is discarded because its w > M

Iteration 4:

Obtain S₁³ by adding pair (p₄, w₄) = (16, 14) to each pair of S³

S₁³ = S³ + (16, 14)

= { (16, 14), (28, 22), (38, 31), (30, 26), (42, 34) }

Obtain S⁴ by merging and purging S³ and S₁³.

S⁴ = MERGE_PURGE (S³, S₁³)

= { (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 S⁴, i.e. (28, 22)

(28, 22) ∈ S⁴ but (28, 22) ∉ S³

So set x_n = x₄ = 1

Update,        

p = p – p₄ = 28 – 16 = 12

w = w – w₄ = 22 – 14 = 8

n = n – 1 = 4 – 1 = 3

Now n = 3, pair (12, 8) ∈ S³ and (12, 8) ∈ S²

So set x_n = x₃ = 0

n = n – 1 = 3 – 1 = 2

Now n = 2, pair(12, 8) ∈ S² but (12, 8) ∉ S¹

So set x_n = x₂ = 1

Update,        

p = p – p₂ = 12 – 12 = 0

w = w – w₂ = 8 – 8 = 0

Problem size is 0, so stop.

Optimal solution vector is (x₁, x₂, x₃, x₃) = (0, 1, 0, 1) Thus, this approach selects pair (12, 8) and (16, 14) which gives profit of 28.

Example: Generate the sets Sⁱ, 0 ≤ i ≤ 3 for following knapsack instance. N = 3, (w₁, w₂, w₃) = (2, 3, 4) and (p₁, p₂, p₃) = (1, 2, 5) with M = 6. Find optimal solution.

Solution:

Initially, S⁰ = {(0, 0) }

Iteration 1:

Obtain S₁⁰ by adding pair (p₁, w₁) = (1, 2) to each pair of S⁰ 

S₁⁰ = S⁰ + (1, 2) = {(1, 2)}

Obtain S¹ by merging and purging S⁰ and S₁⁰

S¹ = MERGE_PURGE (S⁰, S₁⁰)

= { (0, 0), (1, 2) }

Iteration 2:

Obtain S₁¹ by adding pair (p₂, w₂) = (2, 3) to each pair of S¹

S₁¹ = S¹ + (2, 3) = {(2, 3), (3, 5)}

Obtain S² by merging and purging S¹ and S₁¹

S² = MERGE_PURGE(S¹, S₁¹)

= { (0, 0), (1, 2), (2, 3), (3, 5) }

Iteration 3:

Obtain S₁² by adding pair (p₃, w₃) = (5, 4) to each pair of S²

S₁² =  S² + (5, 4) = {(5, 4), (6, 6), (7, 7), (8, 9) }

Obtain S³ by merging and purging S² and S₁² .

S³ = MERGE_PURGE (S², S₁²)

= { (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 S³, i.e. (6, 6)

(6, 6) ∈ S³ but (6, 6) ∉ S²

So set x_n = x₃ = 1

Update,  

p = p – p₃ = 6 – 5 = 1

w = w – w₃ = 6 – 4 = 2

Now n = 2, pair(1, 2) ∈ S² and (1, 2) ∈ S¹

So set x_n = x₂ = 0

Now n = 1, pair(1, 2) ∈ S¹ but (1, 2) ∉ S⁰

So set x_n =   x₁ = 1

Optimal solution vector is (x₁, x₂, x₃) = (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