Activity Scheduling With Profits
Goal: still no overlap allowed; maximize profit of activities (not max number of activities)
Copyright By PowCoder代写 加微信 powcoder
Greedy algs won’t work anymore.
Just for fun, let’s eliminate one greedy alg.
Greedy by max profit.
Counterexample: Activity 1: start 1, finish 10, profit 50
Activity 2: start 2, finish 3, profit 40
Activity 3: start 6, finish 8, profit 40
OPT is 80, greedy gets 50, greedy is toast.
You can also show that earliest finish time is wrong now, too.
Activity 1: start 1, finish 10, profit 1
Activity 2: start 6, finish 20, profit 10000000
———-
Example of p array
Activities [start time, finish time)
Activity 1: [3, 7)
Activity 2: [5, 10)
Activity 3: [8, 20)
What’s p[3]? 1
Activity 1: [3, 7)
Activity 2: [5, 10)
Activity 3: [15, 20)
Now p[3] is 2
Activity 1: [3, 7)
Activity 2: [5, 10)
Activity 3: [1, 20)
Now p[3] is 0
You can make this p array before running an algorithm to find the optimal. In the sample Python code I provided, I just use a p() function… but that is slow. For practice, try replacing this by the p array!
———-
If you have no overlap among any activities, then for any i
p[i] = i-1
If you exclude activity i: … continue with rec_opt(i-1)
If you include activity i: … continue with rec_opt(i-1)
You have two calls, each of which is on a value just one less than the value for the original call
———-
Could our OPT array ever look like this?
[0, 3, 7, 12, 2]
No: because as we’re allowed to consider more and more activities, max profit can only increase
———-
Knapsack, greedy algorithms won’t work
Greedy by highest value first?
Counterexample:
W = 10 (weight capacity of knapsack is 10)
Item 1: value 10, weight 9
Item 2: value 8, weight 5
Item 3: value 8, weight 5
Greedy gets value 10. OPT is 16.
All greedies are wrong; e.g.
-lowest weight first
-various ratios between item values and weights
———-
Suppose we decide to include item n in the optimal solution S.
What would go wrong if we tried to recurse on the first n-1 items and knapsack weight capacity W.
(We’re supposed to be using W- wn, but I want to think about what happens if we use W by mistake)
Maybe the recursion gives us items whose weight is W or close to it
Then, including item n could put us above the weight capacity W
———-
N[4][10]. What will we store here?
Max value we can store in a knapsack with weight capacity 10, using a subset of the first 4 items
max value we we can store in knapsack with weight capacity 8, using the first 0 items
Max value we can store in knapsack of weight 0, using first 5 items
———-
v is array of item values
w is array of item weights
v[i] and w[i] give the value and item for item i
n is number of items
W is knapsack weight capacity
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]
What's our runtime here?
O(nW), i.e. number of items * weight capacity of knapsack
This looks efficient, but it is actually not polynomial time.
e.g. not like sorting, O(n log n)
Let's say n is 10 and W is 1000.
Our algorithm will take 10*1000 = 10000 steps
Let's say n is 10 and W is 10000.
Now, with that one extra keystroke, our algorithm explodes to 10*10000 = 100000 steps
There's a reason we can't come up with an efficient algorithm just in terms of n. e.g. we can't do O(n^2) or O(n^3):
Knapsack is called NP-hard. Take CSC363 🙂
Our algorithm is good if w is small.
e.g. maybe W is just n^2
Then we have nW = n*n^2 = O(n^3)
----------
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
Runtime here is O(n)
----------
Fill in the table for
v = [3, 2, 4, 4],
w = [4, 3, 2, 3], and
What will be the values in the top row; i.e. row 0 (0 items allowed).
0 0 0 0 0 0 0
How about row 1? (i.e. first item is allowed)
0 0 0 0 3 3 3
Fill in row 2, row 3, row 4, using our pseudocode
Each row requires solutions only from the previous row