CSC373H Lecture 4
September 29, 2021
Copyright By PowCoder代写 加微信 powcoder
Back to Activity Scheduling
▶ Input: set of activities a1, 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 better 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 S consists of optimally scheduling a1,a2,…,an−1
▶ If an ∈ S, then the rest of S consists of optimally scheduling the activities that finish before an starts
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 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 our solution 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...
▶ For each element x that is unknown, mem_opt(x) makes two recursive calls and then the element is not unknown anymore
▶ This can happen at most n times, so the total number of calls to mem_opt is 2n
▶ Each call does a constant amount of work outside of the recursive calls
▶ 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...
while i > 0:
if OPT[i] == OPT[i-1]: # i not included
i <- i - 1
else: # i included
S <- S + {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: individual subproblems are solved 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. our profit scheduling problem) or a multi-dimensional array (coming right up!)
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
▶ Suppose that there were a more valuable 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
▶ 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 by using items 1 to i in knapsack of weight capacity j
Knapsack: Step 3
▶ If number of allowed items or max allowable weight is 0, then optimal value is 0
▶ Otherwise, we try both options — excluding and including item i — and pick the better one
0, if i = 0 or j ≤ 0 max{N[i−1,j],N[i−1,j−wi]+vi} ifi>0andj>0
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 filled in before we try to compute N[i,j]
Knapsack: Step 4…
def knapsack(v, w, n, W):
for j in [1, 2, …, W]:
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, ..., W]:
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):
result <- []
while i > 0:
if N[i, j] == N[i-1, j]:
i <- i - 1
result.append(i)
j <- j - w[i]
i <- i - 1
return result
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com