Solve the fractional Knapsack problem:Greedy on the value per pound vi/wiEach time,taketheitemwithmaximumvi/w;.If exceeds W,take fractions of theitemExample: (1, 5$), (2, 9$), (3, 12$), (3, 11$) and w=454.54.03.667V;/w; :First:(1, 5$),Second: (2, 9$), Third: 1/3 (3, 12$)4.3,1,Total W:Can only take part of itemPage62026/9/22CS4335DesignandAnalysisofAlgorithms/WANGLusheng
2026/9/22 CS4335 Design and Analysis of Algorithms/WANG Lusheng Page 6 Solve the fractional Knapsack problem: Greedy on the value per pound vi/wi . Each time, take the item with maximum vi/wi . If exceeds W, take fractions of the item. Example: (1, 5$), (2, 9$), (3, 12$), (3, 11$) and w=4. vi/wi : 5 4.5 4.0 3.667 First: (1, 5$), Second: (2, 9$), Third: 1/3 (3, 12$) Total W: 1, 3, 4. Can only take part of item
Proof of correctness: (The hard part)LetX=iiiz...ikbetheoptimal items taken.ijWiConsider the item j : (vj w) with the highest v/w.if jis notused in X (the optimal solution),i2W2Wgetridof some items with total weightwj (possiblyfractionalitems)Wi +W2+..wp-1 +q%wp=wjand add item j.(sincefractional itemsareallowed,wecandoit.)Total value is increased. Why?V +V2 +...+Vp-1 +q%vpVp-l)+g%v=W, ×(=)+W,×("2)+..+W-+×(W≤x()+W2×(二)+.+Wp-+×()+q%w,x(二)W=(w +W2 +..+Wp-I +q%w,)x()=W,×(")=y1One more item selected by greedy is added toXRepeattheprocess,Xischangedtocontainall itemsselectedbyinWkgreedy WITHOUT decreasing the total value taken by the thiefPage72026/9/22CS4335Design andAnalvsis ofAlgorithms/WANGLusheng
2026/9/22 CS4335 Design and Analysis of Algorithms/WANG Lusheng Page 7 Proof of correctness: (The hard part) X i1 w1 i2 w2 wj . . . ip wp . . . ikwk j j j j j j p p j j p j j p j j j j p p p p p p p p v w v w w v w w w q w w v q w w v w w v w w v w w v q w w v w w v w w v w v v v q v = + + + + = = + + + + = + + + + + + + + − − − − − − ( . % ) ( ) ( ) ( ) ( ) . ( ) % ( ) ( ) ( ) . ( ) % ( ) . % 1 2 1 1 2 1 1 1 1 2 2 2 1 1 1 1 2 1
The O-1 knapsack problem cannotbe solved optimally by greedyCounter example: (moderate part)W=10Items found:(6pounds, 12dollars) 2, (5pounds, 9 dollar) 1.8(5pounds, 9 dollars) 1.8, (3pounds, 3 dollars) 1,(3 pounds, 3 dollars) 1.If we first take (6,12)accordingto greedy algorithmthen solution is (6,12),(3,3) (total value is 12+3=15)However,a better solution is (5,9),(5,9)with totalvalue 18.To show that a statement does not hold, we only have to givean example.Page82026/9/22CS4335DesignandAnalysisofAlgorithms/WANGLusheng
2026/9/22 CS4335 Design and Analysis of Algorithms/WANG Lusheng Page 8 The 0-1 knapsack problem cannot be solved optimally by greedy Counter example: (moderate part) W=10 Items found: (6pounds, 12dollars) 2, (5pounds, 9 dollar) 1.8 , (5pounds, 9 dollars) 1.8, (3pounds, 3 dollars) 1, (3 pounds, 3 dollars) 1. If we first take (6, 12) according to greedy algorithm, then solution is (6, 12), (3, 3) (total value is 12+3=15). However, a better solution is (5, 9), (5, 9) with total value 18. To show that a statement does not hold, we only have to give an example
Interval SchedulingInterval scheduling. Job j starts at s; and finishes at fj.Twojobscompatibleiftheydon'toverlap-Goal:find maximum subset of mutuallycompatible jobsA subset ofmutuallybcompatiblesjobs: (c, f)dghTime01234567891011Page92026/9/22CS4335DesignandAnalysisofAlgorithms/WANGLusheng
2026/9/22 CS4335 Design and Analysis of Algorithms/WANG Lusheng Page 9 A subset of mutually compatibles jobs: {c, f}
IntervalScheduling:GreedyAlgorithmsGreedytemplate.Considerjobsinsomeorder.Takeeachjobprovidedit's compatiblewiththe onesalreadytaken..[Earlieststarttime] Considerjobsinascendingorderof starttime sj..[Earliest finish time] Consider jobs in ascending order of finishtime f.[Shortestinterval]Considerjobsinascendingorderofintervallength fj - Sj..[Fewest conflicts] For each job,countthe number of conflictingjobs Cj. Schedule in ascending order of conflicts Cj.Page 102026/9/22CS4335DesignandAnalysisofAlgorithms/WANGLusheng
2026/9/22 CS4335 Design and Analysis of Algorithms/WANG Lusheng Page 10