贪心算法（两个实例)
例一：调度问题
问题：由n项任务，每项任务的加工时间已知，从零时刻开始陆续加入一台机器上去加工，每个任务完成的时间是从0时刻到任务加工截至的时间。
求总完成时间（所有任务完成时间最短计划方案）
解：任务集合{1，2，3，4，5}
加工时间：t1=3,t2=8,t3=5,t4=10,t5=15
排序：t1<t3<t2<t4<t5
贪心算法的解：
| 3 | 5 | 8 | 10 | 15 |
0 3 8 16 26 41
t总=3+（3+5）+（3+5+8）+（3+5+8+10）+（3+5+8+10+15）
=3*5+5*4+8*3+10*2+15
=94
问题建模：
输入任务集：
{1，2，3，4，......n}
第j项任务加工时间：tj∈Z+，j=1,2,3,4.....n
输出调度I，S的排列，i1,i2,i3,.....in,
t(I)= n/k=1∑(n-k+1)
解使得I*t(I*)值是最小：
贪心算法策略：加工时间按最短先做。
算法：加工时间按从小到大排序，依次加工。
证明：加入调度f的第i，j项任务相邻且有逆序。即ti>tj,交换任务i和j得到调度g
| f | ti | tg | |
| 9 | tg | ti |
带入公式：
t(I)= n/k=1∑(n-k+1)
的：tg-ti<0
直觉不一定正确：
| 标号 | 1 | 2 | 3 | 4 |
| 重量 | 3 | 4 | 5 | 2 |
| 价值 | 7 | 9 | 9 | 2 |
思路：贪心算法：单位重量价值大的优先，总重不超过6
7/3>9/4>9/5>1
1,2,3,4
贪心算法的解：{1，4}重量5，价值9
更好的解：{2，4}重量6，价值11
算法设计：
- 问题建模
- 选择什么算法？如何描述这个算法？
- 这个算法是否所有的实列都得到最优解？如何证明？
- 如果不是能否证明？
例二投资问题
问题：m元钱，投资n个项目，效益函数fi(x)，表示第i个投资项目x元的效益，i=1,2,3,......n,求如何分配每个项目的钱使得收入效益最大？
实例：5万元，投给四个项目：
| x | f1(x) | f2(x) | f3(x) | f4(x) |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 11 | 0 | 2 | 20 |
| 2 | 12 | 5 | 10 | 21 |
| 3 | 13 | 10 | 30 | 22 |
| 4 | 14 | 15 | 32 | 23 |
| 5 | 15 | 20 | 40 | 24 |
