CP 312: Algorithms
Module 6: Dynamic Programming
Eugene Zima
Text readings: CLRS, (sections 15.3, 15.4)
Wilfrid Laurier University
Fall 2025
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 1 / 18
Integer Knapsack
Problem specification:
We are given n objects and a knapsack.
Each object i has a positive weight wi and a positive value vi .
The knapsack can carry a weight not exceeding W . Fill the
knapsack so that the value of objects in the knapsack is maximized.
Brute force:
Try all possibilities. An object can be in or out and we sum weights
to be sure we are not over W . This has complexity Θ(n2n ).
Greedy:
At each step add the object with the highest vi /wi ratio. Does not
work. Counterexample?
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 2 / 18
Integer Knapsack - DP
Recall that objects are numbered from 1 to n.
Definition of a subproblem
Let V [i, j] be the maximum value of the objects, selected from the
first i objects, that can fit into a knapsack with upper weight limit
j (the optimal value will be found in V [n, W ]).
Key observation:
We either use object i in the optimal solution or we do not.
Suppose object i is not in the Knapsack. Then there is no
difference between V [i − 1, j] and V [i, j].
Suppose object i is in the Knapsack. Our claim, for this case, is
that V [i, j] = V [i − 1, j − wi ] + vi .
Consider an optimal selection extracted from the first i − 1 objects
with a weight limitation of j − wi .
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 3 / 18
Integer Knapsack: Derivation of the Recurrence
Looking at only these first i − 1 objects, we can assume we have
an optimal selection that is not more valuable than those chosen
from the first i − 1 objects as used in V [i, j].
This is true because:
A more valuable selection from objects 1 to i − 1 could be
extended with object i and we would get a total value in excess of
V [i, j] in contradiction of the fact that V [i, j] is optimal. So the
value of V [i, j] must be vi plus the optimal solution for the first
i − 1 objects with a weight limitation of j − wi .
Considering the above facts we are able to make up the following
recurrence for V [i, j]:
V [i, j] = max{V [i − 1, j], vi + V [i − 1, j − wi ]}
Base case: V [0, j] = 0.
Order of computation:
Use row-order from top-left down to the bottom-right corner.
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 4 / 18
Knapsack Problem: Pseudo-code for DP
for j := 0 to W do
V[0,j]:=0;
for i := 1 to n do
for j := 1 to W do
sol := V[i-1, j];
if (w[i] <= j) then
othersol := V[i-1, j-w[i]] + v[i];
if (othersol > sol) then
sol := othersol;
V[i, j] := sol;
return V[n, W];
Complexity? Θ(nW ). Is it good or bad???
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 5 / 18
Integer Knapsack: Notes on Pseudo-code
Note
We can make the program more memory efficient.
Note that to compute value V [i, j], we need only the cells from the
previous line and to the left of V [i − 1, j] (including V [i − 1, j]).
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 6 / 18
for j := 0 to W do
V[j] := 0;
for i := 1 to n do
for j := W downto 1 do
sol := V[j];
if (w[i] <= j) then
othersol := V[j-w[i]] + v[i];
if (othersol > sol) then
sol := othersol;
V[j] := sol;
return V[W];
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 7 / 18
Integer Knapsack: Notes on Pseudo-code
More simplifications..
for j := 0 to W do
V[j] := 0;
for i := 1 to n do
for j := W downto 1 do
if (w[i] <= j) then
othersol := V[j-w[i]] + v[i];
if (othersol > V[j]) then
V[j] := othersol;
return V[W];
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 8 / 18
Integer Knapsack: Notes on Pseudo-code
Recovery of the solution added
for j := 0 to W do
V[j] := 0; D[j] := 0;
for i := 1 to n do
for j := W downto 1 do
if (w[i] <= j) then
othersol := V[j-w[i]] + v[i];
if (othersol > V[j]) then
V[j] := othersol; D[j]:= i;
print V[W];
\\ recover the items in knapsack
j:=W;
while (j>0) and (D[j]>0) do
print(D[j]); j:=j-w[D[j]];
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 9 / 18
Minimum Length Triangulation
Problem 4.4
Minimum Length Triangulation v1
Instance: n points q1 , · · · , qn in the Euclidean plane that form a
convex n − gon P.
Find: A triangulation of P such that the sum Sc of the lengths of
the n − 3 chords is minimized.
Problem 4.5
Minimum Length Triangulation v2
Instance: n points q1 , · · · , qn in the Euclidean plane that form a
convex n − gon P.
Find: A triangulation of P such that the sum Sp of the perimeters
of the n − 2 triangles is minimized.
Let L denote the perimeter of P. Then we have that Sp = L + 2Sc .
Hence the two versions have the same optimal solutions.
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 10 / 18
Problem Decomposition
We consider version 2 of the problem.
The edge qn q1 is in a triangle with a third vertex qk , where
k ∈ 2, · · · , n − 1.
For a given k, we have:
1 the triangle q1 qk qn ,
2 the polygon with vertices q1 , · · · , qk ,
3 the polygon with vertices qk , · · · , qn .
The optimal solution will consist of optimal solutions to the two
subproblems in (2) and (3), along with the triangle in (1).
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 11 / 18
Recurrence Relation
For 1 ≤ i < j ≤ n, let S[i, j] denote the optimal solution to the
subproblem consisting of the polygon having vertices qi , · · · , qj .
Let ∆(qi , qk , qj ) denote the perimeter of the triangle having
vertices qi , qk , qj .
Then we have the recurrence relation
S[i, j] = min {∆(qi , qk , qj ) + S[i, k] + S[k, j] : i < k < j}
the base cases are given by
S[i, i + 1] = 0
for all i.
We compute all S[i, j] with j − i = c, for c = 2, 3, · · · , n − 1.
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 12 / 18
Weighted Interval Scheduling
Problem 4.6
Problem: Weighted Interval Scheduling.
Instance: A set I of n intervals [s1 , f1 ], · · · , [sn , fn ] with weights
ω1 , · · · , ωn .
Question:
P Find subset S of disjoint intervals that maximizes
i∈S i ω .
Greedy approach does not work (example?)
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 13 / 18
Denote: OPT (I ) - optimum set S; ωOPT (I ) - corresponding weight.
The structure of optimal solution:
Consider interval i: it is either in OPT
S (I ) or not.
If i ∈ OPT (I ) then OPT (I ) = {i} OPT (I ′ ), where I ′ denotes
intervals disjoint from i.
If i ̸∈ OPT (I ) then OPT (I ) = OPT (I − {i}). Therefore
ωOPT (I ) = max ωOPT (I −{i}) , ωi + ωOPT (I ′ )
Using this directly one ends up with exponential running time
(solving subproblems for 2n subsets of I ).
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 14 / 18
Rename the intervals, by sorting if necessary, so that
f1 ≤ f2 ≤ · · · ≤ fn .
Denote p(j) the largest index i < j such that interval i is disjoint
from the interval j.
Let opt(j) be the weight of optimal solution that considers
intervals 1, 2, · · · , j.
Then opt(0) = 0 and
opt(j) = max {ωj + opt(p(j)), opt(j − 1)}
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 15 / 18
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 16 / 18
Sort intervals according to finish time
Compute p[j] for each j
opt[0]=0
for j from 1 to n
opt[j]= max{opt[j-1], opt[p[j]]+w[j]}
Output opt[n]
Complexity?
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 17 / 18
Solution recovery ...
j = n
while (j>=0) do
if (opt[p[j]]+w[j] > opt[j-1])
print j
j = p[j]
else
j = j-1
E. Zima (WLU) Module 6: Dynamic Programming Fall 2025 18 / 18