贪心算法

贪心算法的本质

• 做出在当前看来最好的选择
• 自顶向下地解决问题

贪心算法基本要素

• 最优子结构
• 贪心选择

贪心算法的例子

活动安排问题：

利用贪心算法，解决下列活动安排问题

1. 给出代表所选择活动的集合A的值（布尔值）
2. 说明使用该算法最多能安排几个活动
3. 活动的序号分别是什么

解题思路：

1. 按照活动结束的时间进行非减排序
2. 根据所排顺序及活动时间是否冲突创建布尔（boolean）表并填入boolean值
3. 根据布尔表得出安排的活动

普通背包问题：

利用贪心算法，解决下列背包问题：

背包容量为5，共有4个物品，其重量w={2, 4, 6, 1}，价值v={5, 6, 3, 3} 。 给出解决问题的步骤 给出最优值（背包中物品的总价值）和最优解（放入背包中每个物品的比例）

1. 解题步骤：

• 按v/w={2.5, 1.5, 0.5, 3}对物品进行排序结果为(编号): {4, 1, 2, 3}

• 依次将物品放入背包中 x[4]=1, 剩余容量c=5-1=4 x[1]=1, 剩余容量c=4-2=2 x[2]=0.5, 剩余容量c=2-4*0.5=0
  X[3]=0, c =0 （这一步可省略）

2. 放入背包中的物品总价值为：5+0.5*6+0+3=11 3. 放入背包中的物品为 x = [1, 0.5, 0, 1]，即编号为1和4的物品全部放入背包中，编号为2的物品的1/2放入背包中，编号为3的物品不放入背包中

最优装载问题：

利用贪心算法，解决下列最优装载问题

共有3个集装箱，其重量为w={2, 4, 1}，集装箱的载重量为5 给出解决问题的步骤以及结果（轮船上最大集装箱数量以及装入轮船上集装箱的编号）

1. 解题步骤：

• 按重量对集装箱从小到大进行排序结果为(编号): {3, 1, 2}

• 依次将集装箱装上轮船 x[3]=1, 剩余容量c=5-1=4 x[1]=1, 剩余容量c=4-2=2 w[2]>c, 循环结束

2. 装上轮船集装箱数量为：2 3. 装上轮船的集装箱为 x = [1,0,1]，即编号为1和3的集装箱装上轮船

构造哈夫曼树：

假设某文件共含有6个字符，其出现的频率如下：

根据该频率构造哈夫曼树时，优先队列的出队顺序是什么？ 给出最终构造出的哈夫曼树

• 采用贪心算法构造哈夫曼树时，可采用优先队列实现最小频度子树的选择
• 规定构造哈夫曼树时，左子树的频度<右子树的频度

Dijkstra算法（迪杰斯特拉算法）：

题目：用Dijkstra算法计算下图从源顶点1到其它顶点间最短路径，并给出中间过程（ u，S及dist）

答案：