Dynamic Programming

Algorithm types

• Algorithm types we will consider include:

➢ Simple recursive algorithms
➢ Brute force algorithms
➢ Randomized algorithms
➢ Divide and conquer algorithms
➢ Greedy algorithms
➢ dynamic programming algorithms
 Dynamic Programming

• Another strategy for designing algorithms is dynamic

programming
➢ A meta technique, not an algorithm
(like divide & conquer)
➢ The word “programming” is historical and predates
computer programming

• Use when problem breaks down into recurring small

subproblems
 Dynamic Programming

• Dynamic programming solves problems by combining the

solutions to sub problems.

• Paradigms:
➢ Divide and conquer
➢ Greedy Algorithm
➢ Dynamic programming
 Dynamic programming

• It is used, when the solution can be recursively described

in terms of solutions to subproblems (optimal
substructure).

• Algorithm finds solutions to subproblems and stores

them in memory for later use.

• More efficient than “brute-force methods”, which solve

the same subproblems over and over again.
 Comparison with divide-and-conquer
• Divide-and-conquer algorithms split a problem into
separate subproblems, solve the subproblems, and combine
the results for a solution to the original problem
➢ Example: Quicksort
➢ Example: Mergesort

• Divide-and-conquer algorithms can be thought of as top-

down algorithms
• In contrast, a dynamic programming algorithm proceeds by
solving small problems, then combining them to find the
solution to larger problems
• Dynamic programming can be thought of as bottom-up
 Dynamic Programming (DP)
• Like divide-and-conquer, solve problem by combining the
solutions to sub-problems.

• Differences between divide-and-conquer and DP:

➢ Independent sub-problems, solve sub-problems
independently and recursively, (so same
sub(sub)problems solved repeatedly)

➢ Sub-problems are dependent, i.e., sub-problems share

sub-sub-problems, every sub(sub)problem solved just
once, solutions to sub(sub)problems are stored in a
table and used for solving higher level sub-problems.
Properties of a problem that can be solved
with dynamic programming
• Simple Subproblems
➢ We should be able to break the original problem to
smaller subproblems that have the same structure

• Optimal Substructure of the problems

➢ The solution to the problem must be a composition of
subproblem solutions
 Dynamic Programming Example:

• Longest Common Subsequence

• 0-1 Knapsack problem

• Matrix Multiplicatiom
 Longest Common Subsequence (LCS)
• DNA analysis, two DNA string comparison.
• DNA string: a sequence of symbols A,C,G,T.
➢ S=ACCGGTCGAGCTTCGAAT

• Subsequence (of X): is X with some symbols left out.

➢ Z=CGTC is a subsequence of X=ACGCTAC.
• Common subsequence Z (of X and Y): a subsequence of X and
also a subsequence of Y.
➢ Z=CGA is a common subsequence of both X=ACGCTAC
and Y=CTGACA.
• Longest Common Subsequence (LCS): the longest one of
common subsequences.
➢ Z' =CGCA is the LCS of the above X and Y.
• LCS problem: given X=<x1, x2,…, xm> and Y=<y1, y2,…, yn>,
find their LCS. 10
 Longest Common Subsequence
• Longest common subsequence (LCS) problem:
given X=<x1, x2,…, xm> and Y=<y1, y2,…, yn>, find their
LCS.

➢ Brute-force algorithm: For every subsequence of x,

check if it’s a subsequence of y
• How many subsequences of x are there?
• What will be the running time of the brute-force
alg?
 LCS Algorithm

• if |X| = m, |Y| = n, then there are 2m subsequences of x; we

must compare each with Y (n comparisons)
• So the running time of the brute-force algorithm is O(n 2m)

• Notice that the LCS problem has optimal substructure:

solutions of subproblems are parts of the final solution.
 LCS DP –step 1: Optimal Substructure
• Characterize optimal substructure of LCS.

• Let X=<x1, x2,…, xm> (= Xm) and Y=<y1,

y2,…,yn> (= Yn) and Z=<z1, z2,…, zk> (= Zk) be
any LCS of X and Y,
➢ 1. if xm= yn, then zk= xm= yn, and Zk-1 is the LCS of Xm-1
and Yn-1.
➢ 2. if xm yn, then zk  xm implies Z is the LCS of Xm-1
and Yn.
➢ 3. if xm yn, then zk  yn implies Z is the LCS of Xm and
Yn-1.

13
 LCS DP –step 2:Recursive Solution

• What the theorem says:

➢If xm= yn, find LCS of Xm-1 and Yn-1, then append xm.
➢If xm  yn, find LCS of Xm-1 and Yn and LCS of Xm
and Yn-1, take which one is longer.

• c[i,j] is the length of LCS of Xi and Yj .

c[i − 1, j − 1] + 1 if x[i] = y[ j ],
c[i, j ] = 
 max( c[i, j − 1], c[i − 1, j ]) otherwise
14
 LCS Algorithm

• First we’ll find the length of LCS. Later we’ll modify the
algorithm to find LCS itself.
• Define Xi, Yj to be the prefixes of X and Y of length i and j
respectively
• Define c[i,j] to be the length of LCS of Xi and Yj
• Then the length of LCS of X and Y will be c[m,n]

c[i − 1, j − 1] + 1 if x[i] = y[ j ],
c[i, j ] = 
 max( c[i, j − 1], c[i − 1, j ]) otherwise
 LCS recursive solution
c[i − 1, j − 1] + 1 if x[i] = y[ j ],
c[i, j ] = 
 max( c[i, j − 1], c[i − 1, j ]) otherwise

• When we calculate c[i,j], we consider two cases:

• First case: x[i]=y[j]: one more symbol in strings X and Y
matches, so the length of LCS Xi and Yj equals to the length
of LCS of smaller strings Xi-1 and Yi-1 , plus 1
 LCS recursive solution

c[i − 1, j − 1] + 1 if x[i] = y[ j ],
c[i, j ] = 
 max( c[i, j − 1], c[i − 1, j ]) otherwise

• Second case: x[i] != y[j]

• As symbols don’t match, our solution is not improved, and the
length of LCS(Xi , Yj) is the same as before (i.e. maximum of
LCS(Xi, Yj-1) and LCS(Xi-1,Yj)
 LCS recursive solution

c[i − 1, j − 1] + 1 if x[i] = y[ j ],
c[i, j ] = 
 max( c[i, j − 1], c[i − 1, j ]) otherwise

• We start with i = j = 0 (empty substrings of x and y)

• Since X0 and Y0 are empty strings, their LCS is always
empty (i.e. c[0,0] = 0)
• LCS of empty string and any other string is empty, so for
every i and j: c[0, j] = c[i,0] = 0
 LCS Example

We’ll see how LCS algorithm works on the following example:

• X = ABCB
• Y = BDCAB

What is the Longest Common Subsequence

of X and Y?
LCS(X, Y) = BCB
X =AB C B
Y= BD CAB
 j 0 1 2 3 4 5
i Yj B D C A B

0 Xi

A
1

2 B

3 C

4 B

X = ABCB; m = |X| = 4
ABCB
Y = BDCAB; n = |Y| = 5
BDCAB
Allocate array c[5,4]
 ABCB

j 0 1 2 3 4 5
BDCAB
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0

2 B
0

3 C 0

4 B 0

for i = 1 to m c[i,0] = 0
for j = 1 to n c[0,j] = 0
 ABCB

j 0 1 2 3 4 5
BDCAB
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0

2 B
0

3 C 0

4 B 0

if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
 ABCB

j 0 1 2 3 4 5
BDCAB
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0 0 0

2 B
0

3 C 0

4 B 0

if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
 ABCB

j 0 1 2 3 4 5
BDCAB
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0 0 0 1

2 B
0

3 C 0

4 B 0

if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
 ABCB

j 0 1 2 3 4 5
BDCAB
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0 0 0 1 1

2 B
0

3 C 0

4 B 0

if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
 ABCB

j 0 1 2 3 4 5
BDCAB
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0 0 0 1 1

2 B
0 1

3 C 0

4 B 0

if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
 ABCB

j 0 1 2 3 4 5
BDCAB
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0 0 0 1 1

2 B
0 1 1 1 1

3 C 0

4 B 0

if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
 ABCB

j 0 1 2 3 4 5
BDCAB
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0 0 0 1 1

2 B
0 1 1 1 1 2

3 C 0

4 B 0

if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
 ABCB

j 0 1 2 3 4 5
BDCAB
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0 0 0 1 1

2 B
0 1 1 1 1 2

3 C 0 1 1

4 B 0

if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
 ABCB

j 0 1 2 3 4 5
BDCAB
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0 0 0 1 1

2 B
0 1 1 1 1 2

3 C 0 1 1 2

4 B 0

if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
 ABCB

j 0 1 2 3 4 5
BDCAB
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0 0 0 1 1

2 B
0 1 1 1 1 2

3 C 0 1 1 2 2 2

4 B 0

if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
 ABCB
j 0 1 2 3 4 5 BDCAB
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0 0 0 1 1

2 B
0 1 1 1 1 2

3 C 0 1 1 2 2 2

4 B 0 1

if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
 ABCB
j 0 1 2 3 4 5 BDCAB
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0 0 0 1 1

2 B
0 1 1 1 1 2

3 C 0 1 1 2 2 2

4 B 0 1 1 2 2

if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
 ABCB
j 0 1 2 3 4 5 BDCAB
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0 0 0 1 1

2 B
0 1 1 1 1 2

3 C 0 1 1 2 2 2

4 B 0 1 1 2 2 3
if ( Xi == Yj )
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
 LCS Length Algorithm

LCS-Length(X, Y)
1. m = length(X) // get the # of symbols in X
2. n = length(Y) // get the # of symbols in Y
3. for i = 1 to m c[i,0] = 0 // special case: Y0
4. for j = 1 to n c[0,j] = 0 // special case: X0
5. for i = 1 to m // for all Xi
6. for j = 1 to n // for all Yj
7. if ( Xi == Yj )
8. c[i,j] = c[i-1,j-1] + 1
9. else c[i,j] = max( c[i-1,j], c[i,j-1] )
10. return c
 LCS Algorithm Running Time

• LCS algorithm calculates the values of each

entry of the array c[m,n]
• So what is the running time?
O(m*n)
since each c[i,j] is calculated in constant time,
and there are m*n elements in the array
Algorithm runs in O(m*n), which is much better than the brute-force
algorithm: O(n 2m)
 How to find actual LCS

• So far, we have just found the length of LCS, but not LCS
itself.
• We want to modify this algorithm to make it output Longest
Common Subsequence of X and Y
Each c[i,j] depends on c[i-1,j] and c[i,j-1]
or c[i-1, j-1]
For each c[i,j] we can say how it was acquired:

2 2 For example, here

2 3
c[i,j] = c[i-1,j-1] +1 = 2+1=3
 How to find actual LCS - continued
• Remember that
c[i − 1, j − 1] + 1 if x[i] = y[ j ],
c[i, j ] = 
 max( c[i, j − 1], c[i − 1, j ]) otherwise

So we can start from c[m,n] and go backwards

Whenever c[i,j] = c[i-1, j-1]+1, remember x[i] (because x[i]

is a part of LCS)

When i=0 or j=0 (i.e. we reached the beginning), output

remembered letters in reverse order
 Finding LCS
j 0 1 2 3 4 5
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0 0 0 1 1

2 B
0 1 1 1 1 2

3 C 0 1 1 2 2 2

4 B 0 1 1 2 2 3
 Finding LCS (2)
j 0 1 2 3 4 5
i Yj B D C A B

0 Xi
0 0 0 0 0 0

A
1 0 0 0 0 1 1

2 B
0 1 1 1 1 2

3 C 0 1 1 2 2 2

4 B 0 1 1 2 2 3
LCS (reversed order): B C B
Dynamic programming
0-1 Knapsack problem
 Review: Dynamic programming

• DP is a method for solving certain kind of problems

• DP can be applied when the solution of a problem includes

solutions to subproblems

• We need to find a recursive formula for the solution

• We can recursively solve subproblems, starting from the

trivial case, and save their solutions in memory

• In the end we’ll get the solution of the whole problem

 Knapsack problem
There are two versions of the problem:
(1) “0-1 knapsack problem” and
(2) “Fractional knapsack problem”

(1) Items are indivisible; you either take an item

or not. Solved with dynamic programming
(2) Items are divisible: you can take any fraction

of an item. Solved with a greedy algorithm.

 0-1 Knapsack problem

• Given a knapsack with maximum capacity W, and a set S

consisting of n items

• Each item i has some weight wi and benefit value bi (all wi

, bi and W are integer values)

• Problem: How to pack the knapsack to achieve maximum

total value of packed items?
 0-1 Knapsack problem:
an example
Weight Benefit value
wi bi
Items
3
2
4
This is a knapsack 3

4 5
Max weight: W = 20
5 8

W = 20

9 10
 0-1 Knapsack problem

• Problem, in other words, is to find

max  bi subject to w W i
iT iT

The problem is called a “0-1” problem, because each item

must be entirely accepted or rejected.
 0-1 Knapsack problem: brute-force
approach
Let’s first solve this problem with a straightforward algorithm

• Since there are n items, there are 2n possible combinations

of items.

• We go through all combinations and find the one with the

most total value and with total weight less or equal to W

• Running time will be O(2n)

 0-1 Knapsack problem: brute-force
approach
• Can we do better?
• Yes, with an algorithm based on dynamic
programming
• We need to carefully identify the subproblems
 Recursive Formula
 B[k − 1, w] if wk  w
B[k , w] = 
max{ B[k − 1, w], B[k − 1, w − wk ] + bk } else

• The best subset of Sk that has the total weight w, either

contains item k or not.

• First case: wk>w. Item k can’t be part of the solution,

since if it was, the total weight would be > w, which is
unacceptable

• Second case: wk <=w. Then the item k can be in the

solution, and we choose the case with greater value
 0-1 Knapsack Algorithm
for w = 0 to W
B[0,w] = 0
for i = 0 to n
B[i,0] = 0
for w = 0 to W
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Running time
for w = 0 to W O(W)
B[0,w] = 0
for i = 0 to n Repeat n times
B[i,0] = 0
for w = 0 to W O(W)
< the rest of the code >
What is the running time of this algorithm?

O(n*W)
Remember that the brute-force algorithm
takes O(2n)
 Example

Let’s run our algorithm on the

following data:

n = 4 (# of elements)
W = 5 (max weight)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
 Example (2)
i 0 1 2 3 4
W
0 0

1 0

2 0

3 0

4 0

5 0

for w = 0 to W
B[0,w] = 0
 Example (3)
i 0 1 2 3 4
W
0 0 0 0 0 0

1 0

2 0

3 0

4 0

5 0

for i = 0 to n
B[i,0] = 0
 Example (4) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0
i=1
2 0 bi=3 3: (4,5)
3 0
wi=2 4: (5,6)
4 0
w=1
5 0
w-wi =-1
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (5) Items:
i 0 1 2 3 4 1: (2,3)
W
0 0 0 0 0 0 2: (3,4)
i=1
1 0 0 3: (4,5)
2 0 3 bi=3 4: (5,6)
3 0
wi=2
4 0
w=2
5 0
w-wi=0
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (6) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0
i=1
2 0 3 bi=3 3: (4,5)
3 0 3
wi=2 4: (5,6)
4 0
w=3
5 0
w-wi=1
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (7) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0
i=1
2 0 3 bi=3 3: (4,5)
3 0 3
wi=2 4: (5,6)
4 0 3
w=4
5 0
w-wi=2
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (8) Items:
i 0 1 2 3 4 1: (2,3)
W
0 0 0 0 0 0 2: (3,4)
i=1
1 0 0 3: (4,5)
2 0 3 bi=3 4: (5,6)
3 0 3
wi=2
4 0 3
w=5
5 0 3
w-wi=2
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (9) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 i=2
2 0 3
3: (4,5)
bi=4
3 0 3 4: (5,6)
4 0 3 wi=3
5 0 3
w=1
if wi <= w // item i can be part of the solution
w-wi=-2
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (10) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 i=2
2 0 3 3
3: (4,5)
bi=4
3 0 3 4: (5,6)
4 0 3 wi=3
5 0 3
w=2
if wi <= w // item i can be part of the solution
w-wi=-1
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (11) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 i=2
2 0 3 3
3: (4,5)
bi=4
3 0 3 4 4: (5,6)
4 0 3 wi=3
5 0 3
w=3
if wi <= w // item i can be part of the solution
w-wi=0
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (12) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 i=2
2 0 3 3
3: (4,5)
bi=4
3 0 3 4 4: (5,6)
4 0 3 4 wi=3
5 0 3
w=4
if wi <= w // item i can be part of the solution
w-wi=1
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (13) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 i=2
2 0 3 3
3: (4,5)
bi=4
3 0 3 4 4: (5,6)
4 0 3 4 wi=3
5 0 3 7
w=5
if wi <= w // item i can be part of the solution
w-wi=2
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (14) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 0 i=3
2 0 3 3 3
3: (4,5)
bi=5
3 0 3 4 4 4: (5,6)
4 0 3 4 wi=4
5 0 3 7
w=1..3
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (15) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 0 i=3
2 0 3 3 3
3: (4,5)
bi=5
3 0 3 4 4 4: (5,6)
4 0 3 4 5 wi=4
5 0 3 7
w=4
if wi <= w // item i can be part of the solution
w- wi=0
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (15) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 0 i=3
2 0 3 3 3
3: (4,5)
bi=5
3 0 3 4 4 4: (5,6)
4 0 3 4 5 wi=4
5 0 3 7 7
w=5
if wi <= w // item i can be part of the solution
w- wi=1
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (16) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 0 0 i=3
2 0 3 3 3 3
3: (4,5)
bi=5
3 0 3 4 4 4 4: (5,6)
4 0 3 4 5 5 wi=4
5 0 3 7 7
w=1..4
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (17) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 0 0 i=3
2 0 3 3 3 3
3: (4,5)
bi=5
3 0 3 4 4 4 4: (5,6)
4 0 3 4 5 5 wi=4
5 0 3 7 7 7
w=5
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Comments

• This algorithm only finds the max possible value

that can be carried in the knapsack
• To know the items that make this maximum value,
an addition to this algorithm is necessary
• Please see LCS algorithm from the previous
lecture for the example how to extract this data
from the table we built
 Conclusion
• Dynamic programming is a useful technique
of solving certain kind of problems
• When the solution can be recursively
described in terms of partial solutions, we
can store these partial solutions and re-use
them as necessary
• Running time (Dynamic Programming
algorithm vs. naïve algorithm):
➢LCS: O(m*n) vs. O(n * 2m)
➢0-1 Knapsack problem: O(W*n) vs. O(2n)