Module 4

DYNAMIC PROGRAMMING: Three basic examples, The Knapsack Problem

and Memory Functions, Warshall’s and Floyd’s Algorithms.
THE GREEDY METHOD: Prim’s Algorithm, Kruskal’s Algorithm, Dijkstra’s
Algorithm, HuffmanTrees and Codes.
 Greedy Method
Prim’s Algorithm, Kruskal’s Algorithm, Dijkstra’s Algorithm,
Huffman trees and Codes.
Greedy Technique
• A greedy algorithm is an algorithm that finds a solution to
problems in the shortest time possible. It picks the path that
seems optimal at the moment without regard for the overall
optimization of the solution that would be formed.
 Minimum Cost Spanning Tree
What is a spanning tree ?
Definition: A spanning tree is a tree in which all nodes are connected
without forming a closed path or circuit. Formally, a spanning tree of a graph
G is defined as a subgraph
G' = (V',E') with following properties.
V' = V
G' is connected and Acyclic
E' i.e. No. of edges is (V-1)
• For example, Consider the graph shown below Note: G=(V,E) be an undirected connected
20 graph
1 2

10 30

3 4
40

The various spanning trees of this graph are shown below.

1.
20
1 2

10
Cost = 10+20+40 = 70
3 4
40
2 1 2

Cost = 10 + 40 + 30 = 80
10 30

3 4
40

20
1 2
3
Cost = 10 + 20 + 30 = 60
10 30

3 4

1 20 2
4
30 Cost = 20 + 40 + 30 = 90

3 4
40
 What is a Minimum Cost Spanning trees ?
Definition : A minimum spanning tree of a given graph G is a spanning
tree whose cost is minimum.

20
Example: 1 2
Graph
10 30

3 4
40

20
1 2
Minimum Cost Spanning Tree
10 30
Cost = 10 + 20 + 30 = 60
3 4
❖ To find a minimum cost spanning tree of a given
graph, there are two algorithms are there
namely:
1. Prim’s Algorithm
2. Kruskal’s Algorithm

The main objectives of the above two algorithms are same, i.e to find
the minimum cost spanning tree of a given graph.
 Prim’s Algorithm
• Prim’s Algorithm constructs a minimum spanning tree through a
sequence of expanding subtrees.
• The initial subtree in such a sequence consists of a single vertex
selected arbitrarily from the set ‘V’ of the graph’s vertices.
• On each iteration, we expand the current tree in the greedy
manner by simply attaching to it the nearest vertex.
• The algorithm stops after all the graph’s vertices have been
included in the tree being constructed. Since the algorithm
expands a tree by exactly one vertex on each of its iterations, the
total number of such iterations is n-1, where n is the number
vertices in the graph.
Example 1: Apply prim’s algorithm to the
following graph.
1
b c

6
4 4
3

5 5 d
a f

2
6 8

e
Sl Visited Nodes (Vᴛ) Unvisited Nodes Edge from visited to unvisited nodes Minimum Edge e*=(v*, Minimum Cost Spanning
No. (V-Vᴛ) (Vᴛ to V-Vᴛ) u*)

1 - a, b, c, d, e, f - -
2 a b, c, d, e, f a–b=3
a–e=6 a–b=3
a–f=5
3 a, b c, d, e, f a–e=6 1
b
a–f=5 b–c=1
b–c=1 3 4
b–f=4
4 a, b, c d, e, f a–e=6 a f
a–f=5
b–f=4 b–f=4 2
c–d=6
c–f=4 e
5 a, b, c, f d, e a–e=6
c–d=6 f–e=2
f–d=5
f–e=2
6 a, b, c, f, e d c–d=6 Minimum Cost is 1
f–d=5 f–d=5
e–d=8
Prim’s Algorithm
Example 2 : Apply Prim’s Algorithm to the
following graph.
2
10 50
40 25
3
1 35
45

5 15
30 55

4 20 6
Time Complexity
• The time complexity in the average case is typically
O((V + E) log V), where V is the number of vertices and
E is the number of edges.
 Kruskal’s Algorithm
• The Kruskal’s algorithm begins by sorting the graph’s edges in non
decreasing order of their weights.
• Then, starting with the empty subgraph, it scans this sorted list
adding the next edge on the list to the current subgraph if such an
inclusion does not create a cycle and simply skipping the edge
otherwise.
Example 1: Apply Kruskal’s algorithm to find minimum
spanning tree of the following graph.

1
b c

4 4 6
3

5 5
a f d

2
6 8

e
Sl. No. Edge Cost Status Minimum Cost Spanning Tree

1 b–c 1 ✓

2 e–f 2 ✓
1
3 a–b 3 ✓ b c

4 b–f 4 ✓
3 4
5 c–f 4 X
6 a–f 5 X 5
a f d
7 d–f 5 ✓
2
8 a–e 6 X
9 c–d 6 X
e
10 d–e 8 X Minimum Cost is 15
Example 2: Apply Kruskal’s algorithm to find minimum
spanning tree of the following graph.

10 50

1 25
40 3
45 35

30 5
15

55

4 6
20
Sl. No. Edge Cost Status Minimum Cost Spanning Tree

1 1–2 10 ✓ 2

2 3–6 15 ✓ 10
25
3 4–6 20 ✓ 1 3
35
4 2–6 25 ✓
5 1–4 30 X
5
15
6 3–5 35 ✓
7 2–5 40 X
8 1–5 45 X 4 6
20
9 2–3 50 X
10 5–6 55 X Minimum Cost is 105
Kruskal’s Algorithm
Disjoint Subsets and Union-Find Algorithms
• Given a set {1, 2, …, n} of n elements.
• Initially each element is in a different set.
▪ {1}, {2}, …, {n}
• An intermixed sequence of union and find operations is
performed.
• A union operation combines two sets into one.
▪ Each of the n elements is in exactly one set at any time.
• A find operation identifies the set that contains a particular
element.
• makeset(x) creates a one-element set {x}. It is assumed that this operation
can be applied to each of the elements of set S only once.
• find(x) returns a subset containing x.
• union(x, y) constructs the union of the disjoint subsets Sx and Sy
containing x and y, respectively, and adds it to the collection to replace Sx
and Sy, which are deleted from it.
Tree Representation of sets
Union of sets
Union Operation
• Union(i,j)
▪ i and j are the roots of two different trees, i != j.
• To unite the trees, make one tree a subtree of the other.
▪ parent[j] = i
Union Example
7

13 8 3 22 6

4 5
10
9
11 30
2 20 16 14 12

1
• Union(7,13)
Result of A Find Operation
• Find(i) is to identify the set that contains element i.
• In most applications of the union-find problem, the user does not
provide set identifiers.
• The requirement is that Find(i) and Find(j) return the same value
iff elements i and j are in the same set.

2 9 11 30 5 13

Find(i) will return the element that is in the tree root.

 Single Source Shortest Paths: Dijkstra’s
Algorithm
• The single source shortest path problem is the one, where in we compute
the shortest path(distance) from a given source vertex Vs to all other vertices
in the graph.
• In other words, given a graph G=(V, E) and a source vertex Vs, we find the
shortest distance from Vs to every other vertex Vd in V.
• This problem is not defined for negative numbers
• This is possible using Dijkstra’s Algorithm.
 Single Source Shortest Paths: Dijkstra’s Algorithm
function dijkstra(G, S)
for each vertex V in G
distance[V] <- infinite
previous[V] <- NULL
If V != S, add V to Priority Queue Q
distance[S] <- 0
while Q IS NOT EMPTY
U <- Extract MIN from Q
for each unvisited neighbour V of U
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
return distance[], previous[]
Example 1: Solve the following instances of the single source shortest
paths problem with vertex 1 as the source

1
10 100
20 5
2

50 60
5
3 4
10
Solution: The cost adjacency matrix of the
given graph is

1 2 3 4 5
1 0 10 ∞ 20 100
2 ∞ 0 50 ∞ ∞
3 ∞ ∞ 0 ∞ 5
4 ∞ ∞ 10 0 60
5 ∞ ∞ ∞ ∞ 0
Source Vertex is 1
1 2 3 4 5
0 10 ∞ 20 100
u=2
dist = 10
10 + 50 = 60 10 + ∞= ∞ 60+ 5 = 65
60 20
u=4
dist = 20

20 + 10 = 30 20 + 60 = 80
30 80 u=3
dist = 30

30 + 5 = 35
35
1 to 1 = 0
1 to 2 = 10 (direct edge)
1 to 3 = 30 (Via 4)
1 to 4 = 20 (direct edge)
1 to 5 = 35 (Via 4, 3)
Source Vertex 2
1 2 3 4 5
∞ 0 50 ∞ ∞ u=3
dist = 50

50 + ∞ 50 + ∞ 50 + 5 = 55
∞ ∞ 55 u=5
dist = 55

55 + ∞ 55 + ∞
∞ ∞
2 to 1 = ∞ (no path)
2 to 2 = 0
2 to 3 = 50 (direct edge)
2 to 4 = ∞ (no path)
2 to 5 = 55 (Via 3)
Example 2: Solve the following instances of the single-source
shortest paths problem with vertex ‘a’ as the source.
4 c
b

3 2 5 6

a d e
7 4
Solution: The cost adjacency matrix of the
given graph is
a b c d e
a 0 3 ∞ 7 ∞
b 3 0 4 2 ∞
c ∞ 4 0 5 6
d 7 2 5 0 4
e ∞ ∞ 6 4 0
Source Vertex a
a b c d e
0 3 ∞ 7 ∞ u=b
dist = 3
3+4=7 3+2=5 3+∞
u=d
7 5 ∞ dist = 5

5 + 5 = 10 u=c
5+4=9
7 9 dist = 7

7 + 6 = 13
9
a to a = 0
a to b = 3 (direct edge)
a to c = 7 (Via b)
a to d = 5 (Via b)
a to e = 9 (Via b and d)
Example 3: Solve the following instances of the single-source
shortest paths problem with vertex ‘a’ as the source.
4 c
b

3 2 5 6

a d e
7 4
Solution: The cost adjacency matrix of the
given graph is
a b c d e
a 0 ∞ ∞ 7 ∞
b 3 0 4 ∞ ∞
c ∞ ∞ 0 ∞ 6
d ∞ 2 5 0 ∞
e ∞ ∞ ∞ 4 0
Source Vertex a
a b c d e
0 ∞ ∞ 7 ∞ u=d
dist = 7
7+2=9 7 + 5 = 12 7+∞=∞ u=b
9 12 ∞ dist = 9

9 + 4 = 13 9+∞=∞
u=c
12 ∞ dist = 12

12 + 6 = 18
18
a to a = 0
a to b = 9 (Via d)
a to c = 12 (Via d)
a to d = 7 (direct edge)
a to e = 18 (Via d and c)
Example 4: Solve the following instances of the single-source
shortest paths problem with vertex ‘1’ as the source.
45

50 10
1 2 3

15
20 30
10 35
20

4 5 6
15 3
 Optimal Tree Problem: Huffman Trees and
Codes
• Codeword: Suppose we have to enable a text that comprises
characters from some n-character alphabet by assigning to each
of the text’s characters some sequence of bits called the
codeword.
• Fixed-length encoding: It assigns to each character a bit string of
the same length. This is exactly what the standard ASCII Code
does.
• Variable-length encoding: It assigns codewords of different
lengths to different characters.
Huffman Trees and Codes
➢There are mainly two major parts in Huffman Coding:
• Build a Huffman Tree from input characters.
• Traverse the Huffman Tree and assign codes to characters.
Optimal Tree Problem: Huffman Trees and
Codes
Example 1: Construct a Huffman tree for the following data and
obtain its Huffman code.

Character a b c d e f

Probability/Frequency 5 9 12 13 16 45
Solution : Arrange the characters in ascending order of their probability

Step 1: 14

5 9
a b

Step 2: Character c d Internal e f

node
Frequency 12 13 14 16 45

25

12 13
c d
 Character Internal e Internal f
Step 3:
node node
Frequency 14 16 25 45

30

14 16
e

5 9
a b
 Character Internal Internal f
Step 4: node node
Frequency 25 30 45

55

25
30

12 13 14 16
c d e

5 9
a b
Step 5: Character f Internal node
Frequency 45 55

100
0 1

45 55
f 0 1
30
25
0 1 0 1

12 13 14 16
0 1 e
c d
5 9
a b
It is the Huffman tree construction for the given input, The
resulting codewords are as follows

Character a b c d e f

Probability/Frequency 5 9 12 13 16 45

Codeword 1100 1101 100 101 111 0

Example 2: Construct a Huffman tree for the following data and obtain
its Huffman code and also
a. Encode the text DAD using the code.
b. Decode the text whose encoding is 10011011011101

Character A B C D -

Probability/Frequency 0.35 0.1 0.2 0.2 0.15

 Solution: Arrange the characters in ascending order of their
probability

Step 1 :
Character B - C D A

Probability 0.1 0.15 0.2 0.2 0.35

0.25

0.1 0.15
B -
Step 2 :
Character C D Internal A
node
Probability 0.2 0.2 0.25 0.35

0.4

0.2 0.2
C D
Step 3 : Character Internal A Internal
node node
Probability 0.25 0.35 0.4

0.6

0.35
0.25
A

0.1 0.15
B -
Step 4 : Character Internal Internal
node node
Probability 0.4 0.6

1.0
0 1

0.4
0 1 0.6
0 1

0.2 0.2 0.35

C D 0.25
0 1 A
0.1 0.15
B -
It is the Huffman tree construction for the given input, The
resulting codewords are as follows.
Character A B C D -

Probability 0.35 0.1 0.2 0.2 0.15

Codeword 11 100 00 01 101

a) D A D = 011101 is the Encoding

b)10011011011101 = B A D_AD is the Decoding

Example 3: Construct a Huffman tree for the following data and obtain
its Huffman code and also
a. Encode the text DAD_BE
b. Decode the text whose encoding is 1100110110

Character A B C D E -

Probability 0.5 0.35 0.5 0.1 0.4 0.2

 Huffman’s Algorithm
• Step 1: Initialize n one-node trees and label them with the characters
of the alphabet. Record the frequency of each character in its trees
root to indicate the trees weight. (More generally, the weight of a tree
will be equal to the sum of the frequencies in the tree’s leaves).
• Step 2: Repeat the following operation until a single tree is obtained.
Find two trees with the smallest weight. Make them left and right
subtree of a new tree and record the sum of their weights in the root
of the new tree as its weight.

A tree constructed by the above algorithm is called a Huffman tree. It

defines in the manner described – a Huffman code.
 Dynamic Programming
Three basic examples, The Knapsack Problem and Memory
Functions, Warshall’s and Floyd’s Algorithms.
Three basic examples:
Example 1:Coin Row Problem
Recurrence Relation for Coin-row problem
Coin Row Problem
Example 2:Coin Row Problem
Example 2:Change-making problem
• Find out minimum number of coins to make
change of given amount using given coins.
• Let F (n) be the minimum number of coins whose
values add up to n; it is
• convenient to define F (0) = 0
Coin-Collecting Problem
 General Method
• What is Dynamic Programming ?
Definition: Dynamic Programming is a method of solving the
problem with overlapping sub-problems. This method works by
dividing the problem into subproblems and getting the solution
for the sub problems using which the solution for the given
problem can be obtained. Once a sub problem is solved, the
result is stored in a table and never recalculated. When a sub
problem of earlier instance is encountered, instead of
recalculating the values, it is simply retrieved from the table thus
saving the time.
What are the differences between divide and
conquer and dynamic programming ?
Divide and Conquer Dynamic Programming

1. This is applicable when subproblems are 1. This is applicable when subproblems are not
independent independent

2. The subproblems are solved separately and 2. The original problem is solved by using the
combined to get the solution for the original results of previous sub problems.
problem.

3. Every instance of the subproblem is 3. Only one instance of the subproblem is

recomputed and is not stored computed and stored

4. Not efficient because of recomputations 4. More efficient because recomputations are

not done.
Transitive Closure : Warshall’s Algorithm
• Definition of Transitive Closure:
The transitive closure of a directed graph with n vertices can be
defined as the n-by-n Boolean matrix T={tij} , in which the element in
the ith row ( 1≤ i ≤ n) and jth column ( 1≤ j ≤ n) is 1 if there exists a
nontrivial directed path (i.e, a directed path of a positive length) from
the ith vertex to the jth vertex otherwise, tij is 0
Example 1: Apply Warshall’s Algorithm to compute transitive closure (
path matrix) for the graph shown below.

a b

c d
Solution: The adjacency matrix for the given graph is shown below.

a b c d
a 0 1 0 0
b 0 0 0 1
c 0 0 0 0
d 1 0 1 0
Step 5: R⁴ a b c d
a 1 1 1 1
b 1 1 1 1
c 0 0 0 0
d 1 1 1 1
is the transitive closure of the given graph
Example 3: Apply Warshall’s Algorithm to compute transitive closure (
path matrix) for the graph shown below.

1 2 3

4
Apply Warshall’s Algorithm to compute transitive
closure ( path matrix) for the graph shown
below.??
 All Pairs Shortest Paths : Floyd’s Algorithm

• In all pairs shortest path problem, we find the shortest distance

from all nodes to all other nodes.
• The solution for this problem can be obtained easily using Floyd’s
algorithm.
• The Floyd’s algorithm is the modified version of warshall’s
algorithm. Formally, the problem can be stated as follows.
• Let G=(V,E) be a directed graph where V is set of vertices with n number of
vertices and E is set of edges. Let cost be the cost adjacency matrix for the
graph G such that
➢Cost (i, j) = 0, for all 0 ≤ i < n
➢ Cost (i, j) is the cost associated with the edge (i, j) if there is an edge from i to
j
➢Cost (i, j) = ∞ if there is no edge from i to j
The all-pairs shortest path’s problem is to determine a matrix D (distance
matrix) such that the element dij contains the shortest distance from i to j
Example 1: Solve the all-pairs shortest path problem for the
diagraph shown below using Floyd’s Algorithm.

1 2

3
Solution: The cost adjacency matrix of the given
graph is shown below

1 2 3
1 0 4 11
2 6 0 2
3 3 ∞ 0
Note : Need to remember this formula
(k) (k-1) (k-1) (k-1)
d ij = min { d ij , d ik + d kj }, for K ≥ 1

To find shortest distance from i to j using intermediate

node as K
Step 1: 1 2 3
(0)
D =
1 0 4 11
2 6 0 2
3 3 ∞ 0
(1) (0) (0) (0)
d (2, 3) = min { d (2,3) , d (2, 1) + d (1, 3)} }
(1)
d (2, 3) = min { 2, 6+11}
(1)
d (2, 3) = 2
(1) (0) (0) (0)
d (3, 2) = min { d (3, 2), d (3, 1) + d (1, 2) }
(1)
d (3, 2) = min { ∞ , 3+4}
d(1) (3, 2) = 7
Step 2: 1 2 3
(1)
D =
4 0 4 11
0 6 0 2
7 3 7 0
(2) (1) (1) (1)
d (1, 3) = min { d (1,3) , d (1, 2) + d (2, 3) }
(2)
d (1, 3) = min { 11, 4+2}
(2)
d (1, 3) = 6
(2) (1) (1) (1)
d (3, 1) = min { d (3, 1), d (3, 2) + d (2, 1) }
(2)
d (3, 1) = min { 3 , 7+6}
d (2) (3, 1) = 3
Step 3: 1 2 3
(2)
D =
1 0 4 6
2 6 0 2
3 3 7 0
(3) (2) (2) (2)
d (1, 2) = min { d (1,2) , d (1, 3) + d (3, 2) }
(3)
d (1, 2) = min { 4, 6+7}
(3)
d (1, 2) = 4
(3) (2) (2) (2)
d (2, 1) = min { d (2, 1), d (2, 3) + d (3, 1) }
(3)
d (2, 1) = min { 6 , 2+3}
d (3) (2, 1) = 5
Step 4: 1 2 3
(3) 1 0 4 6
D =
2 5 0 2
3 3 7 0

is the resultant all pairs shortest path matrix ( distance matrix)

Example 2: Solve the all-pairs shortest path problem for the diagraph shown
below using Floyd’s Algorithm.

2
a b
6 7
3

c 1 d
Solution: The cost adjacency matrix of the given
graph is shown below

a b c d
a 0 ∞ 3 ∞
b 2 0 ∞ ∞
c ∞ 7 0 1
d 6 ∞ ∞ 0
The Knapsack problem and Memory Functions
The 0/1 Knapsack Problem

Definition: Given a Knapsack ( bag or Container ) with following

m → Capacity of the Knapsack
n → number of Objects
w → an array consisting of weights w₁ , w₂ , w₃ ……… w n
p → an array consisting of profits p₁ , p₂ , p₃ ……. pn

x → an array consisting of either 0 or 1.

0 in x i represent ith object has not been selected and 1 in x i
represent ith object has been selected
• The main objective is to place the objects into the knapsack so that
maximum profit is obtained and the weights of objects chosen should
not exceed the capacity of knapsack. This problem can be stated as

n
Maximize ∑ Pi Xi
i=1

n
Subject to the Constraint ∑ Wi Xi ≤ M
i=1
 Design Methodology
❖ Let us consider an instance defined by the first i items, 1 ≤ i ≤ n, with weights W₁
,…….. Wᵢ , values P₁ , …… Pᵢ and Knapsack capacity j , 1 ≤ j ≤ W. Let V[ i , j] be the
value of an optimal solution to this instance, i.e., the value of the most valuable
subset of the first i items that into the knapsack of capacity j .
❖ We can divide all the subsets of the first i items that fit the knapsack of capacity j
into two categories: those that do not include the ith item and those that do.
1. Among the subsets that do not include the ith item, the value of an optimal subset
is, by definition, V[ i – 1, j ]
2. Among the subsets that do include the ith item (hence, j - Wᵢ ≥ 0), an optimal
subset is made up of this item and an optimal subset of the first i-1 items that fit into
the knapsack of capacity j-Wᵢ . The value of such an optimal subset is
Pᵢ + V [i – 1, j - Wᵢ]
V[i,j] = V [ i – 1 , j ] , if j < Wᵢ

max { V [ i – 1, j], V [ i -1, j - Wᵢ ] + Pᵢ , if j ≥ Wᵢ

V [0, j] = 0 for j ≥ 0 and

V [ i, 0] = 0 for i ≥ 0
Example 1: Apply the bottom-up dynamic programming
algorithm to the following instance of the Knapsack problem .

item weight value

1 2 $ 12

2 1 $ 10

3 3 $ 20

4 2 $ 15

Capacity , m=5
 Solution : Let, the given data are number of objects, n=4, capacity of the
knapsack m=5, {W₁ , W₂ , W₃ , W₄ } = {2, 1, 3, 2} and profits , { P₁ , P₂ , P₃ ,
P₄ } = { 12, 10, 20, 15 }

V[i,j] max { V [ i -1, j] , V [ i – 1, j – Wᵢ ] + Pᵢ } max Remarks

or profit
V[ i-1,j]

W₁ =2 P₁ = 12
V [ 1, 1 ] V[0,1]=0 0 j < W₁
V [ 1, 2 ] max { V [ 0,2], V[0,0] +12} = 12 12 j ≥ W₁
V [ 1, 3 ] max { V [ 0,3], V[0,1] +12} = 12 12 j ≥ W₁
V [ 1, 4 ] max { V [ 0,4], V[0,2] +12} = 12 12 j ≥ W₁
V [ 1, 5] max { V [ 0,5], V[0,3] +12} = 12 12 j ≥ W₁
V[i,j] max { V [ i -1, j] , V [ i – 1, j – Wᵢ ] + Pᵢ } max Remarks
or profit
V[ i-1,j]

W₂ =1 P₂ = 10
V [ 2, 1 ] max { V [ 1,1], V[1,0] +10} = 10 10 j ≥ W₂
V [ 2, 2 ] max { V [ 1,2], V[1,1] +10} = 12 12 j ≥ W₂
V [ 2, 3 ] max { V [ 1,3], V[1,2] +10} = 22 22 j ≥ W₂
V [ 2, 4 ] max { V [ 1,4], V[1,3] +10} = 22 22 j ≥ W₂
V [ 2, 5] max { V [ 1,5], V[1,4] +10} = 22 22 j ≥ W₂
V[i,j] max { V [ i -1, j] , V [ i – 1, j – Wᵢ ] + Pᵢ } max Remarks
or profit
V[ i-1,j]

W₃ =3 P₃ = 20
V [ 3, 1 ] V [ 2 , 1 ] = 10 10 j < W₃
V [ 3, 2 ] V [ 2 , 2 ] = 12 12 j < W₃
V [ 3, 3 ] max { V [ 2,3], V[2,0] +20} = 22 22 j ≥ W₃
V [ 3, 4 ] max { V [ 2,4], V[2,1] +20} = 30 30 j ≥ W₃
V [ 3, 5] max { V [ 2,5], V[2,2] +20} = 32 32 j ≥ W₃
V[i,j] max { V [ i -1, j] , V [ i – 1, j – Wᵢ ] + Pᵢ } max Remarks
or profit
V[ i-1,j]

W₄ =2 P₄ = 15
V [ 4, 1 ] V [3, 1] = 10 10 j < W₄
V [ 4, 2 ] max { V [ 3,2], V[3,0] +15} = 15 15 j ≥ W₄
V [ 4, 3 ] max { V [ 3,3], V[3,1] +15} = 25 25 j ≥ W₄
V [ 4, 4 ] max { V [ 3,4], V[3,2] +15} = 30 30 j ≥ W₄
V [ 4, 5] max { V [ 3,5], V[3,3] +15} = 37 37 j ≥ W₄
 Capacity, j

0 1 2 3 4 5
Weights
0 0 0 0 0 0 0
& Profits
W₁=2, P₁ = 12 1 0 0 12 12 12 12
i
W₂=1, P₂ = 10 2 0 10 12 22 22 22
W₃=3, P₃ = 20 3 0 10 12 22 30 32
W₄=2, P₄ = 15 4 0 10 15 25 30 37
Knapsack Problem using Memory Functions
 Knapsack Problem using Memory Functions

• This method uses top-down approach to solve the problem and maintains a
table to store the computed results as is done by bottom-up approach.
• Initially, table entries are filled with “-” indicating they have not been
computed.
• When a new value has to be computed, this method checks the
corresponding entry in the table. If this entry is not “-”, the value is
retrieved from the table. Otherwise, it is computed recursively and is stored
in the corresponding location of the table.
Example 1: Apply the memory function method to solve the following
instance of the knapsack problem with capacity m=5

Item Weight Value

1 2 $12
2 1 $10
3 3 $20
4 2 $15
Solution : Let, the given data are number of objects, n=4, capacity of the
knapsack m=5, {W₁ , W₂ , W₃ , W₄ } = {2, 1, 3, 2} and profits , { P₁ , P₂ , P₃ ,
P₄ } = { 12, 10, 20, 15 }
Note: The following relation is used to solve the problem using memory
function.

V[i,j] = V [ i – 1 , j ] , if j < Wᵢ

max { V [ i – 1, j], V [ i -1, j - Wᵢ ] + Pᵢ , if j ≥ Wᵢ

Step 1: Compute, V[4,5] since j ≥ W₄ , Use equation - 2
i = 4, P₄ = 15 , W₄ = 2 , j=5
V [4, 5] = max { V [3, 5] , V[3,3] +15 }
So, Compute V [3,5] and V [ 3,3]

Step 2: Compute, V[3,5] since j ≥ W₃ , Use equation - 2

i = 3, P₃ = 20 , W₃ = 3 , j=5
V [3, 5] = max { V [2, 5] , V[2,2] +20 }
So, Compute V [2,5] and V [ 2,2]
Step 3: Compute, V[3,3] since j ≥ W₃ , Use equation - 2
i = 3, P₃ = 20 , W₃ = 3 , j=3
V [3, 3] = max { V [2, 3] , V[2,0] +20 }
So, Compute V [2,3] and V [ 2,0]

Step 4: Compute, V[2,5] since j ≥ W₂ , Use equation - 2

i = 2, P₂ = 10 , W₂ = 1 , j=5
V [2, 5] = max { V [1, 5] , V[1,4] +10 }
So, Compute V [1,5] and V [ 1,4]
Step 5: Compute, V[2,2] since j ≥ W₂ , Use equation - 2
i = 2, P₂ = 10 , W₂ = 1 , j=2
V [2, 2] = max { V [1, 2] , V[1,1] +10 }
So, Compute V [1,2] and V [ 1,1]

Step 6: Compute, V[2,3] since j ≥ W₂ , Use equation - 2

i = 2, P₂ = 10 , W₂ = 1 , j=3
V [2, 3] = max { V [1, 3] , V[1,2] +10 }
So, Compute V [1,3] and V [ 1,2]
 Step 7: Compute, V[2,0] but V[2,0] = 0

Step 8: Compute, V[1,5] since j ≥ W₁ , Use equation - 2

i = 1, P₁ = 12 , W₁ = 2 , j=5
V [1, 5] = max { V [0, 5] , V[0,3] +12 }
V [1,5] = max { 0, 0+12}
V[1,5] = 12

Step 9: Compute, V[1,4] since j ≥ W₁ , Use equation - 2

i = 1, P₁ = 12 , W₁ = 2 , j=4
V [1, 4] = max { V [0, 4] , V[0,2] +12 }
V [1,4] = max { 0, 0+12}
V [ 1,4] = 12
Step 10: Compute, V[1,2] since j ≥ W₁ , Use equation - 2
i = 1, P₁ = 12 , W₁ = 2 , j=2
V [1, 2] = max { V [0, 2] , V[0,0] +12 }
V [1,2] = max { 0, 0+12}
V [ 1,2] = 12

Step 11: Compute, V[1,1] since j < W₁ , Use equation - 1

i = 1, P₁ = 12 , W₁ = 2 , j=1
V [1, 1] = V [0, 1]
V[1,1] = 0
Step 12: Compute, V[1,3] since j ≥ W₁ , Use equation - 2
i = 1, P₁ = 12 , W₁ = 2 , j=3
V [1, 3] = max { V [0, 3] , V[0,1] +12 }
V [1,3] = max { 0, 0+12}
V[1,3] = 12

Now, Substituting backwards

Step 13: Compute, V[2,3] ( taken from step 6)

V [2, 3] = max { V [1, 3] , V[1,2] +10 }
V [2,3] = max { 12, 12+10}
V [2,3] = 22
Step 14: Compute, V[2,2] (taken from step 5)
V [2, 2] = max { V [1, 2] , V[1,1] +10 }
V [2,2] = max { 12, 0+10}
V[2,2] = 12

Step 15: Compute, V[2,5] ( taken from step 4)

V [2, 5] = max { V [1, 5] , V[1,4] +10 }
V [2,5] = max { 12, 12+10}
V [2,5] = 22
Step 16: Compute, V[3,3] (taken from step 3)
V [3, 3] = max { V [2, 3] , V[2,0] +20 }
V [3,3] = max { 22, 0+20}
V[3,3] = 22

Step 17: Compute, V[3,5] ( taken from step 2)

V [3, 5] = max { V [2, 5] , V[2,2] +20 }
V [3,5] = max { 22, 12+20}
V [3,5] = 32
Step 18: Compute, V[4,5] (taken from step 1)
V [4, 5] = max { V [3, 5] , V[3,3] +15 }
V [4,5] = max { 32, 22+15}
V[4,5] = 37
Capacity, j
0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 0 12 12 12 12
Weights
& Profits 2 0 - 12 22 - 22
3 0 - - 22 - 32
4 0 - - - - 37

So, the Optimal Solution = 37