一、观看PPT教程 

【01】贪心算法

二、练习题（不清楚回头查看有关PPT）

【01】下面有关贪心算法的描述，请改正错误的地方：

①基本思想——贪心算法又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而期望得到的结果是最好或最优的算法。

②贪心算法适用场景——贪心算法通常适用于满足贪心选择性质和最优子结构性质的问题。贪心算法有多种可选的算法框架，关键在于贪心策略的选择，所采用的贪心策略要满足无后效性。

③贪心算法基本要素——最优子结构性质：问题的最优解包含子问题的最优解。这意味着，问题可以分解成若干个子问题，每个子问题可以独立地求解，并且它们的最优解可以组合成原问题的最优解。贪心选择性质：通过每个子问题的最优选择，可以得到整个问题的最优解。这意味着，当我们面对一个问题时，我们可以通过贪心策略来做出局部最优的选择，最终得到全局最优的解。无后效性：当我们做出一个选择后，它对后面的选择没有影响。这意味着，我们在做出一个选择时，只需要考虑当前的局部最优解，而不需要考虑将来的影响。【02】下面是贪心算法的具体步骤，请改正错误的地方：1．把求解的问题分成若干个步骤；2．对每个步骤进行最优化处理；3．连接所有步骤组成原问题的一个解。

【03】选出一定不能用贪心算法实现的问题：

①区间调度问题：给定一组区间，选择尽可能多的区间，使得它们互不重叠。

②高精度数运算问题：至少有一个整数超出了所有数据类型的长度的加减乘除运算。

③零钱找零问题：给定不同面额的硬币和一个金额，找到凑成该金额所需的最少硬币数。

④哈夫曼编码：用变长编码表示字符，使得出现频率高的字符编码短，出现频率低的字符编码长。

⑤背包问题：给定一组物品和一个背包的容量，选择一些物品放入背包中，使得总价值最大。

⑥最小生成树：在n个城市之间铺设光缆，要使这n个城市的任意两个之间都可以通信，目标是要使铺设光缆的总费用最低，这就需要找到带权的最小生成树。【04】下面是“小明有N元（有零有整）的纸币，想去银行将纸币兑换成硬币，银行硬币只有1角，5角，1元三种。请计算出最少换多少个硬币。”的问题的解决代码，请补全漏写的一行：

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

· 

#include <iostream>using namespace std; int minimumCoins(double N){    int count=0;    int amount=N * 10;    int oneYuan=amount / 10;    count += oneYuan;    amount -= oneYuan * 10;    int fiveJiao = amount / 5;    count += fiveJiao;    amount -= fiveJiao * 5;    cout << "换取1元硬币" << oneYuan << "个" << endl;    cout << "换取5角硬币" << fiveJiao << "个" << endl;    cout << "换取1角硬币" << amount << "个" << endl;    return count;}int main(){     double N;    cout << "请输入纸币金额：";  cin >> N;    int result = minimumCoins(N);  cout << "最少换取硬币数为：" << result;  return 0;}

【05】编程题：合并麦子
【06】下面的问题能用贪心算法得到正确的答案吗？请说明理由。

【07】贪心算法总结，请改正错误的地方：

1．贪心算法通常适用于求解最优化问题，但不是所有最优化问题都适用贪心算法；2．问题必须具备最优选择性质和贪心子结构性质，才能使用贪心算法求解；3．贪心算法有时候不能得到全局最优解，但是贪心算法是一种简单而有效的算法思想，在某些问题中，贪心算法可以得到近似最优解；例如：人工智能很多算法都是贪心算法。4．贪心算法实现比较容易，但是证明正确性很难。