CSC373H Lecture 4
Dan Zingaro
October 3, 2016
Back to Activity Scheduling
Input:setofactivitiesa1,a2,…,an
Each activity ai has a start time si , finish time fi , and
nonnegative profit (or worth) wi
Output: subset of activities S such that no activities in S overlap and profit(S) is maximum
Greedy Strategies
This time, greedy by finish time doesn’t work.
Simplest counterexample:
[0, 4) with profit 1, [0, 5) with profit 3
Taking the 1-profit prevents us from taking the 3-profit.
Greedy Strategies…
Let’s try greedy by maximum unit profit (i.e. profit divided by duration).
Doesn’t work. Simplest counterexample:
[0, 4) with profit 1, [0, 20) with profit 3
The 1-profit has a better ratio, but it prevents us from taking the 3-profit!
Recursive Formulation
Greedy strategies are not going to work here
But we can come up with a recursive formulation of the
problem. Maybe that will help?
Start by sorting activities by increasing finish time
Consider optimal schedule S. There are two possibilities for activity an
an∈S,or an̸∈S
Recursive Formulation…
If an ∈ S, then the rest of S consists of optimally scheduling the activities that finish before an starts
If an ̸∈ S, then S consists of optimally scheduling a1,a2,…,an−1
define p[i] to be the largest index j such that a_j
does not overlap a_i
# Return maximum possible profit from a_1,…,a_n
def rec_opt(n):
if n == 0:
return 0
else:
return max(rec_opt(n-1), w_n + rec_opt(p[n]))
Runtime of Recursive Version
Consider a set of n activities where there is no overlap at all
ThenT(n)=2T(n−1)+c
This recurrence has an exponential closed-form, O(2n)!
So, we’ve solved the problem, but in practice it is only useful for small instances or instances with lots of overlap
Solution 1: Memoization
Observation: there are only n + 1 subproblems to solve rec_opt(0), rec_opt(1), …, rec_opt(n)
So, since our recursive algorithm has exponential runtime, we must be solving those same n + 1 subproblems over and over
memoization: store solutions to subproblems in an array so that they can be looked-up rather than recomputed
Solution 1: Memoization…
Let OPT[i] = max profit from scheduling {a_1,…,a_i}
OPT[0] = 0
OPT[1..n] = unknown
def mem_opt(n):
if OPT(n) is unknown:
OPT[n] = max(mem_opt(n-1), w_n + mem_opt(p[n]))
return OPT[n]
Solution 1: Memoization…
Therearenowatmostn+1recursivecalls
Each call does a constant amount of work before possibly
making a recursive call
Ignoring the time for sorting, we have an O(n) algorithm now
This is the best time complexity we can get, but not the best implementation
Overhead of recursive calls
With many activities, recursion depth limit might be reached
Can we eliminate the recursion altogether?
Solution 2: Dynamic Programming
A bottom-up algorithm.
def dyn_opt(n):
OPT[0] = 0
for i in [1,2,…,n]:
OPT[i] = max(OPT[i-1], w_i + OPT[p[i]])
return OPT[n]
Recovering the Activities
So far, our dynamic-programming algorithm gives us the maximum profit, but not the activities that give us this profit
We can use the information in OPT to recover the set of activities
If OPT[i] == OPT[i-1], then the profit using the first i − 1 activities is the same as the profit using the first i activities
So, activity i is not included Otherwise, activity i is included
. . . and we then continue checking with activity p[i]
Recovering the Activities…
S = {}
i=n
while i > 0:
if OPT[i] == OPT[i-1]: # i not included i=i-1
else: # i included
S = S + {i}
i = p[i]
Dynamic Programming
Dynamic programming applies to an optimization problem when we have
Optimal substructure: an optimal solution to a problem consists of optimal solutions to subproblems
Overlapping subproblems: subproblems are repeated many times in the recursive formulation of larger problems
Independent subproblems: solution to one subproblem does not affect the solution of another subproblem
Dynamic Programming Steps
Step 1: describe recursive structure of problem
How can problem be decomposed?
How does the optimal solution to the problem relate to the optimal solutions of the subproblems?
Step 2: define array for the subproblems whose optimal values will be stored
This can be a 1d array (e.g. profit scheduling) or a multi-dimensional array
Step 3: using step 1, describe how the array values from step 2 are related
Dynamic Programming Steps…
Step 4: write iterative algorithm using step 3
The algorithm is bottom-up (no recursion)
It calculates optimal values for each array element
Step 5: use the array to recover the solution that yielded the optimal
This adds code to step 4
It may require storing additional information in step 4
Knapsack Problem
In the knapsack problem, we have n items, each with a value vi and a weight wi
Assume that all wi are positive integers
We also have a weight capacity W of the knapsack
The goal is to maximize the value of items put in the knapsack with the constraint that the weights of the items add up to at most W
Knapsack: Greedy?
Here are two ideas for possible greedy algorithms: Sort from highest vi to lowest vi
Sort from highest vi /wi to lowest vi /wi
Unfortunately these are not correct. Let’s find counterexamples
Knapsack: Step 1
On to dynamic programming!
Order the items in some arbitrary way
Consider an optimal solution S. Two possibilities for item n:
ItisnotinS ItisinS
We don’t know which option is correct, so we will have to try both
We will then choose the one that gives us the better solution
Knapsack: Step 1…
Optimal substructure of Knapsack.
Suppose that the optimal solution S does not contain item n
Then S must contain within it an optimal solution to the Knapsack problem using only the first n − 1 items
Why?
Suppose that there were a better solution for the first n − 1
items than the one used in S
Then we could use that as a better solution than S —
contradiction!
Knapsack: Step 1…
Now suppose that the optimal solution S does contain item n
We argue that S must contain within it an optimal solution to the Knapsack problem using the first n − 1 items with a knapsack capacity of W − wn
Why?
Suppose that there were a more valuable solution for the first
n − 1 items that fits in a knapsack of capacity W − wn
Then we could take that solution, add item n, and have a
better solution than S — contradiction!
Knapsack: Step 2
We have a 2d array this time
One dimension indexes the allowable items
The other dimension indexes the allowable weight
N[i,j] is the most value that we can get from items 1 to i in knapsack of weight j
Knapsack: Step 3
If number of allowed items or max allowable weight is 0, then optimal value is 0
Otherwise, we try including and excluding item i and pick the best one
0, if i = 0 or j ≤ 0 max{N[i−1,j],N[i−1,j−wi]+vi} ifi>0andj>0
N[i,j] =
Knapsack: Step 4
There are only nW subproblems, but they would be solved repeatedly by a naive recursive algorithm
Instead, we use a bottom-up dynamic programming approach
We must solve smaller subproblems before solving larger
subproblems
i.e. We must fill-in the array in such a way that N[i − 1, j] and N[i −1,j −wi] are present before N[i,j] is computed
Knapsack: Step 4…
def knapsack(v, w, n, W):
for j in [1, 2, …, N]:
N[0, j] <- 0
for i in [1, 2, ..., n]:
N[i, 0] <- 0
for i in [1, 2, ..., n]:
for j in [1, 2, ..., N]:
N[i, j] <- max(N[i-1, j], N[i-1, j - w[i]] + v[i])
return N[n, W]
Knapsack: Step 5
def recover(N, w, n, W): i=n
j=W
result = [] while i > 0:
if N[i, j] == N[i-1, j]: i=i-1
else: result.append(i) j = j – w[i] i=i-1
return result