MATHEMATICAL PROGRAMMING

CO 2

Dynamic Programming
 DYNAMIC PROGRAMMING
• Dynamic programming is a technique that breaks the problems
into sub-problems, and saves the result for future purposes so
that we do not need to compute the result again.
• The main use of dynamic programming is to solve
optimization problems.
• Here, optimization problems mean that when we are trying to
find out the minimum or the maximum solution of a problem.

2
CONT..
• The dynamic programming guarantees to find the optimal
solution of a problem if the solution exists.
• The definition of dynamic programming says that it is a
technique for solving a complex problem by first breaking into
a collection of simpler subproblems, solving each subproblem
just once, and then storing their solutions to avoid repetitive
computations.

3
CONT..
• Dynamic programming is powerful design technique for
optimization problems.

• Principle of optimality : “In an optimal sequence of decisions

or choices, each sub sequence must also be optimal”.

4
CONT..
• The principle of optimality is the heart of dynamic
programming.
• It states that to find the optimal solution of the original
problem, a solution of each sub problem also must be
optimal.
• It is not possible to derive optimal solution using dynamic
programming if the problem does not possess the principle of
optimality.

5
HOW DOES THE DYNAMIC PROGRAMMING APPROACH WORK?
• The following are the steps that the dynamic programming follows:
• It breaks down the complex problem into simpler subproblems.
• It finds the optimal solution to these sub-problems.
• It stores the results of subproblems (memorization). The process of
storing the results of subproblems is known as memorization.
• It reuses them so that same sub-problem is calculated more than
once.
• Finally, calculate the result of the complex problem.

6
EXAMPLE
• Suppose we start travelling from
vertex 1 and return back to vertex 1.
• There are various ways to travel
through all the vertices and returns to
vertex 1.
• From the starting vertex 1, we can go
to either vertices 2, 3, or 4, as shown
in the below diagram.

7
CONT..
• From vertex 2, we can go either to
vertex 3 or 4. If we consider vertex
3, we move to the remaining
vertex, i.e., 4. If we consider the
vertex 4 shown in the below
diagram:

8
CONT..
• From vertex 3, we can go to the
remaining vertices, i.e., 2 or 4. If we
consider the vertex 2, then we
move to remaining vertex 4, and if
we consider the vertex 4 then we
move to the remaining vertex, i.e.,
3 shown in the below diagram:

9
CONT..
• From vertex 4, we can go to the
remaining vertices, i.e., 2 or 3. If
we consider vertex 2, then we
move to the remaining vertex,
i.e., 3, and if we consider the
vertex 3, then we move to the
remaining vertex, i.e., 2 shown in
the below diagram:

10
 LIMITATIONS
• The method is applicable to only those problems which
possess the property of principle of optimality.

• Dynamic programming is more complex and time-consuming.

11
 APPLICATIONS OF DYNAMIC PROGRAMMING
• Dynamic programming is used to solve optimization problems.
• It is used to solve many real life problems such as,
• Make a change problem
• Knapsack problem
• Optimal binary search tree
• Travelling salesman problem
• All pair shortest path problem
• Assembly line scheduling
• Multi stage graph problem

12
 TRAVELLING SALESMAN PROBLEM USING
DYNAMIC PROGRAMMING
• Travelling Salesman Problem-
• You are given-
• A set of some cities.
• Distance between every pair of cities.
• Travelling Salesman Problem states-
• A salesman has to visit every city exactly once.
• He has to come back to the city from where he starts his journey.
• What is the shortest possible route that the salesman must follow to
complete his tour?

13
COMPLEXITY ANALYSIS OF TRAVELING SALESMAN PROBLEM

• Dynamic programming creates n. 2n subproblems for n cities.

• Each sub-problem can be solved in linear time.
• Thus the time complexity of TSP using dynamic programming would be
O(n22n).
• It is much less than n! but still, it is an exponent.
• Space complexity is also exponential.

14
EXAMPLE

• Table

1 2 3 4
1 0 10 15 20
2 5 0 9 10
3 6 13 0 12
4 8 8 9 0

15
 Min{35,40,43}=35
1
CONT…
10+25=35 15+25=40 20+23=43
Min{31,25}=25 Min{23,27}=23

Min{29,25}=25 2 3 4
13+18=31 12+13=25 8+15=23 9+18=27
9+20=29 10+15=25

3 4 2 4 2 3
12+8=20 9+6=15 10+8=18 8+5=13 9+6=15 13+5=18

4 3 4 2 3 2

8 6 8 5 6 5

1 1 1 1 1 1

The minimum cost path is 35.

16
ALGORITHM FOR TRAVELING SALESMAN PROBLEM
• Step 1:
• Let d[i, j] indicates the distance between cities i and j.
• Function C[x, V – { x }]is the cost of the path starting from city x.
• V is the set of cities/vertices in given graph.
• The aim of TSP is to minimize the cost function.
• Step 2:
• Assume that graph contains n vertices V1, V2, ..., Vn.
• TSP finds a path covering all vertices exactly once, and the same time
it tries to minimize the overall traveling distance.

17
CONT..
• Step 3:
• Mathematical formula to find minimum distance is stated below:

• C(i,V) = min { d[i, j] + C(j,V – { j }) }, j ∈ V and i ∉ V.

• TSP problem possesses the principle of optimality, i.e. for d[V1,Vn] to be minimum, any
intermediate path (Vi,Vj) must be minimum.

18
PROBLEM
• Solve the traveling salesman problem with the associated cost adjacency matrix using
dynamic programming.
• Table

1 2 3 4
1 0 10 15 20
2 5 0 9 10
3 6 13 0 12
4 8 8 9 0

19
SOLUTION
• Let us start our tour from city 1.
• Step 1:
• Initially, we will find the distance between city 1 and city {2, 3, 4, } without visiting any
intermediate city.
• Cost(x, y, z) represents the distance from x to z and y as an intermediate city.
• Cost(2, Φ, 1) = d[2, 1] = 5
• Cost(3, Φ, 1) = d[3, 1] = 6
• Cost(4, Φ , 1) = d[4, 1] = 8

20
CONT.…
• Step 2:
• In this step, we will find the minimum distance by visiting 1 city as intermediate city.
• C(i,V) = min { d[i, j] + C(j,V – { j }) },

• Cost{2, {3}, 1} = d[2, 3] + Cost(3, Φ, 1) = 9 + 6 = 15

• Cost{2, {4}, 1} = d[2, 4] + Cost(4, Φ, 1) = 10 + 8 = 18
• Cost{3, {2}, 1} = d[3, 2] + Cost(2, Φ, 1) = 13 + 5 = 18
• Cost{3, {4}, 1} = d[3, 4] + Cost(4, Φ, 1) = 12 + 8 = 20
• Cost{4, {3}, 1} = d[4, 3] + Cost(3, Φ, 1) = 9 + 6 = 15
• Cost{4, {2}, 1} = d[4, 2] + Cost(2, Φ, 1) = 8 + 5 = 13

21
CONT.…
• Step 3:
• In this step, we will find the minimum distance by visiting 2 city as intermediate city.
• C(i, V) = min { d[i, j] + C(j,V – { j }) },
• Cost(2, {3, 4}, 1) = min { d[2, 3] + Cost(3, {4}, 1), d[2, 4] + Cost(4, {3}, 1)]}
= min { [9 + 20], [10 + 15] }
= min {29, 25} = 25.
• Cost(3, {2, 4}, 1) = min { d[3, 2] + Cost(2, {4}, 1), d[3, 4] + Cost(4, {2}, 1)]}
= min { [13 + 18], [12 + 13] }
= min {31, 25} = 25.
• Cost(4, {2, 3}, 1) = min{ d[4, 2] + Cost(2, {3}, 1), d[4, 3] + Cost(3, {2}, 1)]}
= min { [8 + 15], [9 + 18] }
= min {23, 27} = 23.

22
CONT.…
• Step 4:
• In this step, we will find the minimum distance by visiting 3 city as intermediate city.
• C(i, V) = min { d[i, j] + C(j,V – { j }) },
• Cost(1, {2, 3, 4}, 1) = min { d[1, 2] + Cost(2, {3, 4}, 1), d[1, 3] + Cost(3, {2, 4}, 1), d[1, 4] + Cost(4, {2, 3}, 1)}
= min { 10 + 25, 15 + 25, 20 + 23}
= min{35, 40, 43} = 35.
• Thus, minimum length tour would be of 35.
• Trace the path:
• Let us find the path that gives the distance of 35.
• Cost(1, {2, 3, 4}, 1) is minimum due to d[1, 2], so move from 1 to 2. Path = {1, 2}.
• Cost(2, {3,4}, 1) is minimum due to d[2,4], so move from 2 to 4. Path = {1, 2, 4}.
• Cost(4, {3}, 1) is minimum due to d[4, 3], so move from 4 to 3. Path = {1, 2, 4, 3}.
• All cities are visited so come back to 1. Hence the optimum tour would be 1 – 2 – 4– 3 – 1.

23
PROBLEM2
• Solve the traveling salesman problem with the associated cost adjacency matrix using
dynamic programming. 1 2 3 4 5
1 - 24 11 10 9
2 8 - 2 5 11
3 26 12 - 8 7
4 11 23 24 - 6
5 5 4 8 11 -

24
SOLUTION

• Let us start our tour from city 1.

• Step 1:
• Initially, we will find the distance between city 1 and city {2, 3, 4, 5} without visiting any
intermediate city.
• Cost(x, y, z) represents the distance from x to z and y as an intermediate city.
• Cost(2, Φ, 1) = d[2, 1] = 24
• Cost(3, Φ, 1) = d[3, 1] = 11
• Cost(4, Φ , 1) = d[4, 1] = 10
• Cost(5, Φ , 1) = d[5, 1] = 9

25
SOLUTION
• Step 2: In this step, we will find the minimum distance
by visiting 1 city as intermediate city.
• Cost{2, {3}, 1} = d[2, 3] + Cost(3, f, 1) = 2 + 11 = 13 • Cost{4, {2}, 1} = d[4, 2] + Cost(2, f, 1) = 23 + 24 = 47
• Cost{2, {4}, 1} = d[2, 4] + Cost(4, f, 1) = 5 + 10 = 15 • Cost{4, {3}, 1} = d[4, 3] + Cost(3, f, 1) = 24 + 11 = 35
• Cost{2, {5}, 1} = d[2, 5] + Cost(5, f, 1) = 11 + 9 = 20 • Cost{4, {5}, 1} = d[4, 5] + Cost(5, f, 1) = 6 + 9 = 15
• Cost{3, {2}, 1} = d[3, 2] + Cost(2, f, 1) = 12 + 24 = 36 • Cost{5, {2}, 1} = d[5, 2] + Cost(2, f, 1) = 4 + 24 = 28
• Cost{3, {4}, 1} = d[3, 4] + Cost(4, f, 1) = 8 + 10 = 18 • Cost{5, {3}, 1} = d[5, 3] + Cost(3, f, 1) = 8 + 11 = 19
• Cost{3, {5}, 1} = d[3, 5] + Cost(5, f, 1) = 7 + 9 = 16 • Cost{5, {4}, 1} = d[5, 4] + Cost(4, f, 1) = 11 + 10 = 21

26
SOLUTION

• Step 3: In this step, we will find the minimum distance by visiting 2 cities as intermediate city.
• Cost(2, {3, 4}, 1) = min { d[2, 3] + Cost(3, {4}, 1), d[2, 4] + Cost(4, {3}, 1)]}
= min { [2 + 18], [5 + 35] }
= min{20, 40} = 20
• Cost(2, {4, 5}, 1) = min { d[2, 4] + Cost(4, {5}, 1), d[2, 5] + Cost(5, {4}, 1)]}
= min { [5 + 15], [11 + 21] }
= min{20, 32} = 20
• Cost(2, {3, 5}, 1) = min { d[2, 3] + Cost(3, {4}, 1), d[2, 4] + Cost(4, {3}, 1)]}
= min { [2 + 18], [5 + 35] }
= min{20, 40} = 20

27
 - 24 11 10 9
8 - 2 5 11
26 12 - 8 7
SOLUTION 11 23 24 - 6
5 4 8 11 -

• Cost(3, {2, 4}, 1) = min { d[3, 2] + Cost(2, {4}, 1), d[3, 4] + Cost(4, {2}, 1)]}
= min { [12 + 15], [8 + 47] }
= min{27, 55} = 27
• Cost(3, {4, 5}, 1) = min { d[3, 4] + Cost(4, {5}, 1), d[3, 5] + Cost(5, {4}, 1)]}
= min { [8 + 15], [7 + 21] }
= min{23, 28} = 23
• Cost(3, {2, 5}, 1) = min { d[3, 2] + Cost(2, {5}, 1), d[3, 5] + Cost(5, {2}, 1)]}
= min { [12 + 20], [7 + 28] }
= min{32, 35} = 32

28
 - 24 11 10 9
8 - 2 5 11
26 12 - 8 7
SOLUTION 11 23 24 - 6
5 4 8 11 -

• Cost(4, {2, 3}, 1) = min{ d[4, 2] + Cost(2, {3}, 1), d[4, 3] + Cost(3, {2}, 1)]}
= min { [23 + 13], [24 + 36] }
= min{36, 60} = 36
• Cost(4, {3, 5}, 1) = min{ d[4, 3] + Cost(3, {5}, 1), d[4, 5] + Cost(5, {3}, 1)]}
= min { [24 + 16], [6 + 19] }
= min{40, 25} = 25
• Cost(4, {2, 5}, 1) = min{ d[4, 2] + Cost(2, {5}, 1), d[4, 5] + Cost(5, {2}, 1)]}
= min { [23 + 20], [6 + 28] }
= min{43, 34} = 34

29
 - 24 11 10 9
8 - 2 5 11
26 12 - 8 7
SOLUTION 11 23 24 - 6
5 4 8 11 -

• Cost(5, {2, 3}, 1) = min{ d[5, 2] + Cost(2, {3}, 1), d[5, 3] + Cost(3, {2}, 1)]}
= min { [4 + 13], [8 + 36] }
= min{17, 44} = 17
• Cost(5, {3, 4}, 1) = min{ d[5, 3] + Cost(3, {4}, 1), d[5, 4] + Cost(4, {3}, 1)]}
= min { [8 + 18], [11 + 35] }
= min{26, 46} = 26
• Cost(5, {2, 4}, 1) = min{ d[5, 2] + Cost(2, {4}, 1), d[5, 4] + Cost(4, {2}, 1)]}
= min { [4 + 15], [11 + 47] }
= min{19, 58} = 19

30
 - 24 11 10 9
8 - 2 5 11
26 12 - 8 7
SOLUTION 11 23 24 - 6
5 4 8 11 -

• Step 4 :
• In this step, we will find the minimum distance by visiting 3 cities as intermediate city.
• Cost(2, {3, 4, 5}, 1) = min { d[2, 3] + Cost(3, {4, 5}, 1), d[2, 4] + Cost(4, {3, 5}, 1), d[2, 5] + Cost(5, {3, 4}, 1)}

= min { 2 + 23, 5 + 25, 11 + 36}

= min{25, 30, 47} = 25
• Cost(3, {2, 4, 5}, 1) = min { d[3, 2] + Cost(2, {4, 5}, 1), d[3, 4] + Cost(4, {2, 5}, 1), d[3, 5] + Cost(5, {2, 4}, 1)}

= min { 12 + 20, 8 + 34, 7 + 19}

= min{32, 42, 26} = 26

31
 - 24 11 10 9
8 - 2 5 11
26 12 - 8 7
SOLUTION 11 23 24 - 6
5 4 8 11 -
• Cost(4, {2, 3, 5}, 1) = min { d[4, 2] + Cost(2, {3, 5}, 1), d[4, 3] + Cost(3, {2, 5}, 1), d[4, 5] + Cost(5, {2, 3}, 1)}

= min {23 + 30, 24 + 32, 6 + 17}

= min{53, 56, 23} = 23
• Cost(5, {2, 3, 4}, 1) = min { d[5, 2] + Cost(2, {3, 4}, 1), d[5, 3] + Cost(3, {2, 4}, 1), d[5, 4] + Cost(4, {2, 3}, 1)}

= min {4 + 30, 8 + 27, 11 + 36}

= min{34, 35, 47} = 34

32
 - 24 11 10 9
8 - 2 5 11
26 12 - 8 7
SOLUTION 11 23 24 - 6
5 4 8 11 -

• Step 5 : In this step, we will find the minimum distance by visiting 4 cities as an intermediate
city.
• Cost(1, {2, 3, 4, 5}, 1) = min { d[1, 2] + Cost(2, {3, 4, 5}, 1), d[1, 3] + Cost(3, {2, 4, 5}, 1), d[1, 4]
+ Cost(4, {2, 3, 5}, 1) , d[1, 5] + Cost(5, {2, 3, 4}, 1)}
= min { 24 + 25, 11 + 26, 10 + 23, 9 + 34 }
= min{49, 37, 33, 43} = 33
• Thus, minimum length tour would be of 33.

33
 - 24 11 10 9
8 - 2 5 11
26 12 - 8 7
SOLUTION 11 23 24 - 6
5 4 8 11 -

• Trace the path:

• Let us find the path that gives the distance of 33.
• Cost(1, {2, 3, 4, 5}, 1) is minimum due to d[1, 4], so move from 1 to 4. Path = {1, 4}.
• Cost(4, {2, 3, 5}, 1) is minimum due to d[4, 5], so move from 4 to 5. Path = {1, 4, 5}.
• Cost(5, {2, 3}, 1) is minimum due to d[5, 2], so move from 5 to 2. Path = {1, 4, 5, 2}.
• Cost(2, {3}, 1) is minimum due to d[2, 3], so move from 2 to 3. Path = {1, 4, 5, 2, 3}.
• All cities are visited so come back to 1. Hence the optimum tour would be 1 – 4 – 5 – 2 – 3 – 1.

34
KNAPSACK PROBLEM USING DYNAMIC PROGRAMMING
• 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.

35
CONT…
• 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.
36
CONT.…
• 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.

37
CONT.…
• Two approaches for solving knapsack using dynamic programming.
• First Approach for Knapsack Problem using Dynamic Programming.
1. 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.
2. 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.

38
CONT.…
• 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

39
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.
• Running time of Brute force approach is O(2n).
• 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 using dynamic programming with memorization is O(n * M).

40
CONT.…
• 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).

41
CONT.…

42
CONT.…
• Boundary conditions would be V [0, i] = V[i, 0] = 0.
• Initial configuration of table.

43
CONT.…
• 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

44
CONT.…
• 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

45
CONT.…
• 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

46
CONT.…
• 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

47
CONT.…
Final table would be,

48
CONT.…
• 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 = { }

49
CONT.…
• 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 = { }

50
CONT.…
• 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}

51
CONT.…
• 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

52
 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 second approach discussed below is more suitable when
problem instance is large.

53
METHOD

• 1. Set S0 = {(0, 0)}

• 2. S1i = {(p, w) | (p – pi) ∈ Si,
(w – wi) ∈ 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

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

55
SOLUTION
• n = 4, • 1. Set S0 = {(0, 0)}
• M = 25, • 2. S1i = {(p, w) | (p – pi) ∈ Si,
• (P1, P2, P3 P4) = (10, 12, 14, 16), (w – wi) ∈ Si }
• (W1, W2, W3, W4) = (9, 8, 12, 14)
• Initially, S0 = { (0, 0) }
• Knapsack capacity is very large, i.e.
• Iteration 1:
25, so tabular approach won’t be
suitable. We will use the set method • Obtain S10 by adding pair (p1, w1) = (10, 9) to
to solve this problem. each pair of S0
• S10 = S0 + (10, 9) = {(10, 9)}

56
CONT….
• n = 4, • S0 = { (0, 0) }
• M = 25, • S10 = S0 + (10, 9) = {(10, 9)}
• (P1, P2, P3 P4) = • Obtain S1 by merging and purging S0 and S10
(10, 12, 14, 16),
• S1 = MERGE_PURGE (S0, S10) = { (0, 0), (10, 9) }
• (W1, W2, W3, W4)
= (9, 8, 12, 14) S0 = { (0, 0) }
S10 = S0 + (10, 9) = {(10, 9)}
S1 = { (0, 0), (10, 9) }

57
CONT….
• n = 4, • Iteration 2:
• M = 25, • Obtain S11 by adding pair (p2, w2) = (12, 8) to each pair of S1
• (P1, P2, P3 P4) = • S11 = S1 + (12, 8) = {(12, 8), (22, 17)}
(10, 12, 14, 16), • Obtain S2 by merging and purging S1 and S11
• (W1, W2, W3, W4) • S2 = MERGE_PURGE(S1, S11) = { (0, 0), (12, 8), (22, 17) }
= (9, 8, 12, 14)
• Pair (10, 9) is discarded because pair (12, 8) dominates (10, 9).
• 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. S1 = { (0, 0), (10, 9) }
S11 = {(12, 8), (22, 17)}
S2 = { (0, 0), (12, 8), (22, 17) }
58
CONT….
• n = 4, • Iteration 3:

• M = 25, • Obtain S12 by adding pair (p3, w3) = (14, 12) to each pair of S2
• S12 = S2 + (14, 12) = { (14, 12), (26, 20), (36, 29) }
• (P1, P2, P3 P4) =
(10, 12, 14, 16), • Obtain S3 by merging and purging S2 and S12 .
• S3 = MERGE_PURGE (S2, S12 ) = { (0, 0), (12, 8), (22, 17), (14, 12), (26, 20) }
• (W1, W2, W3, W4)
• Pair (36, 29) is discarded because its w > M
= (9, 8, 12, 14)
• It also purges all the pairs (p, w) from Si + 1 if w > M, i.e. it weight
exceeds knapsack capacity.
S2 = { (0, 0), (12, 8), (22, 17) }
S12 = S2 + (14, 12) = { (14, 12), (26, 20), (36, 29) }
S3 = { (0, 0), (12, 8), (22, 17), (14, 12), (26, 20) }

59
CONT….
• n = 4, • Iteration 4:

• M = 25, • Obtain S13 by adding pair (p4, w4) = (16, 14) to each pair of S3

• (P1, P2, P3 P4) = • S 1

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

(10, 12, 14, 16), • Obtain S4 by merging and purging S3 and S13.

• (W1, W2, W3, W4) • S4 = MERGE_PURGE (S3, S13) = { (0, 0), (12, 8), (14, 12), (16, 14), (22, 17),
= (9, 8, 12, 14) (26, 20), (28, 22) }
• Pair (38, 31), (30, 26) ,and (42, 34) are discarded because its w > M

S3 = { (0, 0), (12, 8), (22, 17), (14, 12), (26, 20) }
S13 = S3 + (16, 14) = { (16, 14), (28, 22), (38, 31), (30, 26), (42, 34) }
S4 = { (0, 0), (12, 8), (14, 12), (16, 14), (22, 17), (26, 20), (28, 22) }

60
CONT….
• n = 4, • Find optimal solution: Here, n = 4.
• M = 25, S4 = { (0, 0), (12, 8), (14, 12), (16, 14), (22, 17), (26, 20), (28, 22) }

• (P1, P2, P3 P4) = • Start with the last pair in S4, i.e. (28, 22)
(10, 12, 14, 16),
• (28, 22) ∈ S4 but (28, 22) ∉ S3
• (W1, W2, W3, W4)
= (9, 8, 12, 14) • So set xn = x4 = 1
• Update,
• p = p – p4 = 28 – 16 = 12
• w = w – w4 = 22 – 14 = 8

61
CONT….
• n = 4, • n=n–1=4–1=3
• M = 25, • Now n = 3, pair (12, 8) ∈ S3 and (12, 8) ∈ S2
• (P1, P2, P3 P4) = (10, 12, 14,
16),
• So set xn = x3 = 0

• (W1, W2, W3, W4) = (9, 8, • n=n–1=3–1=2

12, 14)
• 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, x4) = (0, 1, 0, 1) Thus, this approach selects
pair (12, 8) and (16, 14) which gives profit 12+16=28.

62