Week 2: Greedy AlgorithmsPagel2026/9/22CS4335 Design andAnalysis ofAlgorithms/WANGLusheng
Week 2: Greedy Algorithms 2026/9/22 CS4335 Design and Analysis of Algorithms/WANG Lusheng Page 1
Greedy Algorithms:A greedy algorithm always makes the choicethat looks best at the moment.It makes a local optimal choice in the hopethat this choice will lead to a globallyoptimal solution.Greedy algorithms yield optimal solutionsfor many (but not all) problems.Page22026/9/22CS4335 Design andAnalysis ofAlgorithms/WANGLusheng
2026/9/22 CS4335 Design and Analysis of Algorithms/WANG Lusheng Page 2 Greedy Algorithms: A greedy algorithm always makes the choice that looks best at the moment. It makes a local optimal choice in the hope that this choice will lead to a globally optimal solution. Greedy algorithms yield optimal solutions for many (but not all) problems
Knapsack problem:?12kgS42kgS215kgk9$104kgPage32026/9/22CS4335Design andAnalvsis ofAlgorithms/WANGLusheng
Knapsack problem: 2026/9/22 CS4335 Design and Analysis of Algorithms/WANG Lusheng Page 3
Knapsack problem:Input: n items: (Wi, V), ..., (Wn, Vn) and a number Wthe i-th item's is worth v; dollars with weight wj.at most W pounds to be carried.Output: Some items which are most valuable andwith total weight at most W.Two versions:0-1 Knapsack: Items cannot be divided into piecesfractionalknapsack: Items can be divided into piecesPage42026/9/22CS4335 Design andAnalysis ofAlgorithms/WANGLusheng
Knapsack problem: Input: n items: (w1 , v1 ), ., (wn , vn ) and a number W the i-th item’s is worth vi dollars with weight wi . at most W pounds to be carried. Output: Some items which are most valuable and with total weight at most W. Two versions: 0-1 Knapsack: Items cannot be divided into pieces fractional knapsack: Items can be divided into pieces 2026/9/22 CS4335 Design and Analysis of Algorithms/WANG Lusheng Page 4
The O-1 Knapsack problem:The 0-1 knapsack problem:Nitems,wherethe i-thitemisworthV;dollarsandweight w;pounds.11p3p4p58p8p88pV,andw;are integers.$3$6$35$8$28$66$Wecan carryatmostW(integer)pounds.HowtotakeasvaluablealoadaspossibleAnitemcannotbedividedintopieces.Thefractional knapsack problem:WThe same setting,but the thief can take fractions of items.W may not be integer.Page52026/9/22CS4335 Design andAnalysis ofAlgorithms/WANGLusheng
2026/9/22 CS4335 Design and Analysis of Algorithms/WANG Lusheng Page 5 The 0-1 Knapsack problem: The 0-1 knapsack problem: N items, where the i-th item is worth vi dollars and weight wi pounds. 11 p 3 p 4p 58 p 8p 88p vi and wi are integers. 3$ 6 $ 35$ 8$ 28$ 66$ We can carry at most W (integer) pounds. How to take as valuable a load as possible. An item cannot be divided into pieces. The fractional knapsack problem: The same setting, but the thief can take fractions of items. W may not be integer. W