上海充通大学 SHANGHAI JLAO TONG UNIVERSITY Computer Algorithm Design and Analysis Lecture 1 Week 13:Greedy and Dynamic Programming Yongxin ZHU,Weiguang SHENG 强 LAMMAMARAU SHANC 1日g
Computer Algorithm Design and Analysis Lecture 1 Week 13: Greedy and Dynamic Programming Yongxin ZHU, Weiguang SHENG
上海充通大学 Greedy Algorithm vs Dynamic SHANGHAI JLAO TONG UNIVERSITY Programming? General idea: Dynamic Programming means Dynamic Planning Greedy algorithm is a special case of dynamic programming Greedy algorithm approaches (approximately sometimes)the global optimum with local optimum Dynamic Programming can handle the optimization issues without local optimum 3/12/2022
3/12/2022 Greedy Algorithm vs Dynamic Programming? General idea: • Dynamic Programming means Dynamic Planning • Greedy algorithm is a special case of dynamic programming • Greedy algorithm approaches (approximately sometimes) the global optimum with local optimum • Dynamic Programming can handle the optimization issues without local optimum
上海充通大学 SHANGHAI JLAO TONG UNIVERSITY Greedy Coin Changing WE NT IE T H C E N T U RY。X SE L E C T I O N S 里迈ESE☒TH Greed is good.Greed is right.Greed works. Greed clarifies,cuts through,and captures the essence of the evolutionary spirit. Gordon Gecko (Michael Douglas) Cashier would say:"Making change with dollars, nickels,and pennies. SH 1日g
Greedy Coin Changing Greed is good. Greed is right. Greed works. Greed clarifies, cuts through, and captures the essence of the evolutionary spirit. - Gordon Gecko (Michael Douglas) Cashier would say: "Making change with dollars, nickels, and pennies
上海充通大学 Coin Changing SHANGHAI JLAO TONG UNIVERSITY Goal.Given currency denominations:1,5,10,25,100,devise a method to pay amount to customer using fewest number of coins. ©EX:34. Cashier's algorithm.At each iteration,add coin of the largest value that does not take us past the amount to be paid. Ex: $2.89
4 Coin Changing Goal. Given currency denominations: 1, 5, 10, 25, 100, devise a method to pay amount to customer using fewest number of coins. Ex: 34¢. Cashier's algorithm. At each iteration, add coin of the largest value that does not take us past the amount to be paid. Ex: $2.89
上海充通大学 SHANGHAI JLAO TONG UNIVERSITY Greedy Algorithm Example1: Minimum Spanning Tree 强 MARARAAA月 奏 SHANG 1日
Greedy Algorithm Example1: Minimum Spanning Tree