Greedy Algorithms
Fractional Knapsack
Job Scheduling on Multi-processors Activity Selection
topic 7: Greedy method
Copyright By PowCoder代写 加微信 powcoder
Algorithm Design Techniques:
Three major design techniques are:
Greedy Method
Divide and Conquer
Dynamic Programming
1- Greedy Method:
This is usually good for optimization problems, where we are looking for a solution by maximizing or minimizing an objective function. For example, maximizing the profit or minimizing the cost.
Usually, coming up with a greedy solution is easy; But often it is more difficult to prove that the algorithm is correct.
General scheme: always make choices that look best at the current step; these choices are final and are not changed later.
topic 7: Greedy method
Example 1: Fractional Knapsack
We broke into expensive spices store with a knapsack of capacity W.
The store contains n spices, and for the ith spice, a bundle of wi
kilos, which can be sold in the market for bi bucks.
Our goal is to fill the knapsack (without exceeding its capacity) with
a combination of the items with maximum profit.
Example:
cumin saffron pepper nutmeg turmeric paprika profit(bi) 6 8 10 4 3 9
Consider knapsack capacity = 4kg
Optimal solutions: {2kg cumin, 2kg saffron} or {2kg saffron,
0.5kg cumin, 1kg turmeric, 0.5kg paprika} (profit = $14)
Formally,find0≤xi ≤wi for1≤i≤nsuchthatni=1xi ≤W
weight (wi)
and n bi × xi is maximized. ( bi is the price per unit, or unit
i=1 wi price for item i.)
topic 7: Greedy method
Fractional Knapsack: General Description
Suppose we have a set S of n items, each with a profit/value bi and
weight wi.
We also have a knapsack of capacity W ,
Assume that each item can be picked at any fraction, that is we can pick 0≤xi ≤wi amountofitemi.
Our goal is to fill the knapsack (without exceeding its capacity) with a combination of the items with maximum profit.
Formally,find0≤xi ≤wi for1≤i≤nsuchthatni=1xi ≤W and n bi × xi is maximized.
Greedy idea: start picking the items with more “value”:
value ≡ bi wi
So let vi = bi . The algorithm will be as follows: wi
The pseudocode is:
Procedure Frac-Knapsack (S,W)
for i ← 1 to n do xi ← 0; vi ← bi
wi CurrentW ← 0
While CurrentW < W do
let i be the next item in S with highest value xi ←min{wi,W−CurrentW}
add xi amount of i to knapsack
CurrentW ← CurrentW + xi
How to find next highest value in each step?
One way is to sort S at the begining based on vi’s in non-increasing order.
Another way is to keep a PQ (max-heap) based on values.
Since we check at most n items, running time is upper bounded by O(n log n).
Since in the WC we check all n items, the lower bound is Ω(n log n).
Hence, running time is Θ(n log n).
topic 7: Greedy method
When and Why Does the Greedy Method Work?
Any problem that can be solved by gready method must have the optimal substructure property: the optimal solution contains optimal solutions to sub-problems that look just like the original problem.
Once we decide on xj then we need to solve the same problem on the remaining instance:
OPTW,⟨w1,b1⟩,...,⟨wn,bn⟩) =
maxj wj xj +OPT W−xj, ⟨w1,b1⟩,...,⟨wj−1,bj−1⟩,⟨wj+1,bj+1⟩,...,⟨wn,bn⟩
It says: “the optimal solution overall must be of the form: taking xj from some commodity, and filling the remaining W − xj room in the knapsack with the optimal set of the remaining n − 1 spices.”
This already points to a recursive nature of the solution.
topic 7: Greedy method
When and Why Does the Greedy Method Work?
The substitution property:
Any optimal solution to the problem can be altered to include our greedy choices without hindering optimality.
We can prove the correctness of a greedy algorithm by showing the substitution property holds.
This is also called greedy-choice property (CLRS p.424; do not worry about relations with dynamic programming (DP); come back to read p.424 after we introduce DP.)
topic 7: Greedy method
Here is what it means for the factional Knapsack problem: Let S = {y1,...,yn} be an optimal solution and
S′ = {x1, . . . , xn} a solution generated by our algorithm.
We have cost(S) ≥ cost(S′) (cost of a solution means the same
as profit or value of a solution). where if S = {x1, . . . , xn}, then
cost(S)=xj·bj .
We want to show: each greedy choice in S′ can be used to replace some portions of one or more items in S so the altered solution of S is still optimal. We will deal with one item at a time.
Terminology: in our greedy algorithm’s solution S′, item 1 is said to be saturated - meaning x1 = min{W, w1}, i.e., we cannot pick anymore of item 1.
topic 7: Greedy method
topic 7: Greedy method
Claim: There exists an optimal solution to the Fractional Knapsack problem where item 1 is saturated.
Proof: Assume the problem’s input is (W, ⟨b1, w1⟩, ..., ⟨bn, wn⟩) and
S = {y1 , . . . , yn } is an optimal solution. For simplicity, assume items
aresortedbyvalue: b1 ≥ b2 ≥...≥ bn w1w2 wn
If y1 = x1 (item 1 is saturated) we are done.
So assume item 1 isn’t saturated.
We alter S to obtain a solution Z = {z1,...,zn} with (i) cost(Z) ≥
cost(S) = OP T and with (ii) item 1 saturated (i.e. z1 =min{W,w1}).
Case 1: There’s still room in the knapsack, namely i yi < W .
We simply add more of item 1 as much as we can.
Set∆=min{W−iyi, x1−y1}(howmuchroomisleftin
the knapsack and how much more of item 1 we can take).
Setz1 =y1 +∆andzj =yj foranyotherj.
By taking more of item 1 the cost of the new solution
{z1,...,zn} is at least that of {y1,...,yn} (= OPT).
topic 7: Greedy method
When and Why Does the Greedy Method Work (Cont’d)
Proof (Cont’d):
Case 2: The knapsack is full, namely i yi = W .
Item 1 isn’t saturated, so y1 < W , so there must be some spice
k s.t. yk > 0. We alter the solution to take less of item k and more of item 1 as much as we can:
Set∆=min{yk,(x1−y1)}
Setz1 =y1 +∆,zk =yk −∆andzj =yj foranyotheritemj.
This cannot decrease the cost
zj·bj −yj·bj =∆·(b1 −bk )≥0 wj wj w1wk
If item 1 is now saturated, we are done. Otherwise, we continue with Case 2 until it becomes saturated.
We can repeat the same argument to show that S can be altered using each of the greedy choices in S′ so that the resulting solution is optimal.
Example 2: Scheduling on Multiple Processors
SupposewehaveasetT ofnjobs,eachjobihasastarttimesi and finish time fi
Each job/task can be performed on one machine and each machine can perform one job at a time
We say two jobs i and j conflict if their times overlap: Eithersi ≤sj
Consider the first time we put a job i on machine k + 1.
So at this time, job i conflicts with all the ”last” jobs on machines
m1 m2 m3 m4 m5
topic 7: Greedy method
So all these (last) jobs start before si and finish after si.
So at time si, all these k jobs plus job i must run in parallel
Therefore, we need at least k + 1 processors.
Thus optimum cannot use only k processors to run even just these k + 1 jobs.
Example 3: Activity Selection
Suppose that we have n jobs, each with a start time si and finish time fi; 0 ≤ si < fi; these are given and are fixed.
We have only one machine to use and the machine can process one job at a time (and once started, a job most be run until its finish time).
Two jobs i and j are said to conflict (or are incompatible) if the two intervals [si,fi) and [sj,fj) overlap.
Goal: schedule a largest subset of non-conflicting jobs on this machine
1st attempt: suppose we sort the jobs based on start time, i.e. s1 ≤s2 ≤...≤sn. Scheduleajobifwecan.
Badexample: s1 =1,s2 =2,s3 =3
f1 = 4, f2 = 3, f3 = 4
The greedy can only schedule job 1 but the optimal is to schedule 2 and 3.
2nd attempt: Try to schedule shorter jobs first, i.e. sort jobs based on fi − si in non-decreasing order and then Schedule a job if we can.
Badexample: s1 =3,s2 =1,s4 =4
f1 = 5, f2 = 4, f3 = 8
The greedy can only schedule job 1 but the optimal is to schedule 2 and 3.
3rd attempt: Sort the jobs based in non-decreasing order of finish time, i.e. f1 ≤f2 ≤...≤fn andthenScheduleajobifwecan.
topic 7: Greedy method
Correctness:
procedure Activity-Selection (S)
Sort activities in S s.t. A←∅; e←0;
for i ← 1 to n do
if si ≥e then A ← A∪{i}
e ← fi return A
f1 ≤ f2 ≤ ... ≤ fn
Note that the running time of this algorithm is Θ(n log n) as it’s the time needed to sort the jobs and each iteration of the loop takes constant time.
In this algorithm A is the set of jobs scheduled by our algorithm and e at any given time is the time at which the last scheduled job finishes (i.e. the earliest time we can schedule the next job).
We prove that this 3rd attempt is correct.
First note that, since we always schedule a new job if its start time si is larger than the finish time of the last scheduled job we get a set of compatible jobs at the end.
topic 7: Greedy method
To complete correctness, we have to show our algorithm obtains an optimum solution.
Promising: we say a schedule after step i is promising if it can be extended to an optimal schedule using a subset of jobs in {i + 1,...,n}.
We prove that after every step i, the partial solution we have is promising.
Formally, let Ai and ei denote the values of A and e after iteration i of
the for-loop, respectively.
NotethatA0 =∅ande=0.
We show that after each iteration i ≥ 0, the decisions we have made so far are all correct in the sense that there is an optimum solution which contains everything we have selected so far and everything that we have decided not to include (so far) does not belong to that optimum either: Lemma: For every 0 ≤ i ≤ n, there is an optimal solution Aopt such that Ai ⊆ Aopt ⊆ Ai ∪{i+1,...,n}.
Notethatifweprovethisforall0≤i≤n,andinparticularfori=nwe have: An ⊆ Aopt ⊆ An ∪ ∅ which implies An = Aopt, i.e. our solution is the same as some optimum solution; this is what we wanted.
We use induction on i to prove the above lemma.
topic 7: Greedy method
topic 7: Greedy method
Base: i = 0, clearly empty schedule can be extended to an optimal one from {1,...,n}; Thus ∅ = A0 ⊆ Aopt ⊆ ∅ ∪ {1,...,n}.
Induction Step: Suppose we have a promising schedule after step i ≥, i.e. there is an optimum solution Aopt such that:
Ai ⊆ Aopt ⊆ Ai ∪{i+1,...,n}
We consider three cases
Case 1: if si+1 < ei so we cannot schedule job i + 1 because it overlaps with one of the previously scheduled ones; i.e. Ai+1 = Ai.
Since Ai ⊆ Aopt, Aopt has the job from Ai that is overlapping with i + 1 as well, so Aopt cannot have i + 1 either. Thus:
Ai+1 = Ai ⊆ Aopt ⊆ Ai+1 ∪ {i + 2, . . . , n}.
Case 2: si+1 ≥ ei; so Ai+1 = Ai ∪ {i + 1}. Case 2A: i+1 ∈ Aopt then
Ai+1 ⊆ Aopt ⊆ Ai+1 ∪ {i + 2,...,n} and we are done. Case 2B: i + 1 ̸∈ Aopt;
Note that si+1 ≥ ei and so i+1 does not conflict with anything in Ai;
On the other hand we cannot add i + 1 to Aopt (otherwise it would have not been an optimum solution); so there must be a job j ∈ Aopt conflicting with i + 1. Since
Aopt ⊆ Ai ∪{i+1,...,n} and since i+1 does not conflict with anything in Ai: j ≥ i + 2.
Let j ≥ i+2 be a job of Aopt with the earliest finish time that is conflicting with i + 1.
All activities in Aopt − Ai − {j} have start-time after fj (or they will overlap with job j); so they do not overlap with job i+1 because i+1 finishes before fj.
So A′opt = (Aopt −{j})∪{i+1} is feasible and has the
same size as Aopt; i.e. it is another optimum solution and Ai+1 ⊆ A′opt ⊆ Ai+1 ∪ {i + 2,...,n}.
topic 7: Greedy method
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com