算法设计笔记（一）调度问题之“贪心算法”
例1：调度问题有n 项任务，每项任务加工时间已知，从0时刻开始陆续安排到一台机器上，加工每个任务的完成时间是从0 时刻到任务加工截止的时间，求: 总完成时间（所有任务完成时间之和）最短的安排方案
贪心算法：按照加工时间（3，5，8，10，15）从小到大安排
分别对应任务1，3，2，4，5，每个任务完成的时间计算都是从0时刻开始到该任务完成结束为止，所以可以得到以下总时间t的计算
接着对这个问题进行建模
输入：任务集：s={1,2…,n},第j项任务加工时间：
输出：调度I,S的排列
目标函数：I的完成时间，
这样就可以得到本题的最优解
最后我们再来回顾以下“贪心算法”
设计策略：加工时间短的先做
算法：根据加工时间从小到大排序，以此加工
算法正确性：对所有输入实例都得到最优解
对某一特定的两个任务假设完成时间分别 为ti和tj,并假设ti>tj，有两种处理方案
方案f:时间长的先做，那么总任务完成时间t1=ti+(ti+tj)
方案g:时间短的先做，那么总任务完成时间t2=tj+(tj+t1)
两方案的时间差为t2-t1=tj-ti<0
这就是贪心算法的一个应用，那么它是不是对所有的问题都是通用的呢？其实不然
反例：有四件物品要装入背包，物品重量和价值如下
背包重量限制是6，问如何选择物品，使不超重的情况下，装入背包的物品价值达到最大？
利用贪心算法：单位重量价值大的优先算，总重不超过6按照Vi/Wj从小到大排序：1，2，3，4
贪心算法的解：{1，4}，重量5，价值9
然而更好的解：{2，4}，重量6，价值11
所以说“贪心算法”在这里并不适用
作者：chenxiaoqinghua
