算法节选11.10课件
以下为《算法节选11.10课件》的无排版文字预览，完整内容请下载
Greedy AlgorithmsOptimization problems minimize or maximize some parameter over all possible inputs.
Among the many optimization problems we will study are:
Finding a route between two cities with the smallest total mileage.
Determining how to encode messages using the fewest possible bits.
Finding the fiber links between network nodes using the least amount of fiber.
Optimization problems can often be solved using a greedy algorithm, which makes the “best” choice at each step. Making the “best choice” at each step does not necessarily produce an optimal solution to the overall problem, but in many instances, it does.
After specifying what the “best choice” at each step is, we try to prove that this approach always produces an optimal solution, or find a counterexample to show that it does not.
The greedy approach to solving problems is an example of an algorithmic paradigm, which is a general approach for designing an algorithm. We return to algorithmic paradigms in Section 3.3.Greedy Algorithms: Making ChangeExample: Design a greedy algorithm for making change (in U.S. money) of n cents with the following coins: quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent) , using the least total number of coins.
Idea: At each step choose the coin with the largest possible value that does not exceed the amount of change left.
If n = 67 cents, first choose a quarter leaving 67?25 = 42 cents. Then choose another quarter leaving 42 ?25 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 lity depends on the denominations available.
For U.S. coins, optimality still holds if we add half dollar coins (50 cents) and dollar coins (100 cents).
But if we allow only quarters (25 cents), dimes (10 cents), and pennies (1 cent), the algorithm no longer produces the minimum number of coins？[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]请点击下方选择您需要的文档下载。
- 新unit2作业
- 研究生复试口语资料_***05
- 文学英语 21春季学期课程手册
- 背完这100个句子
- 新年和圣诞节的区别--英语作文
- 届高考英语应用文写作专题
- 九上U1-4的作文范文
- 届高考 暑假语法专项练习九 并列连词和状语从句
以上为《算法节选11.10课件》的无排版文字预览，完整内容请下载
算法节选11.10课件由用户“jiangniuniu1”分享发布，转载请注明出处