第三讲-贪心法专题讲座.pptVIP

例3.1 已知n=3, M=20, p=(25, 24, 15), w=(18, 15, 10), 其中的四个可行解 例3.2 已知n=4, p=(100, 10, 15, 20), d=(2, 1, 2, 1), 其中的九个可行解： 算法与时间复杂度 FastGreedyJobScheduling(int *d, float *p, int *J, int n) { int k=min {n, max {d[i]}}, F[k+1]; ElemType set[k+1]; for (i=0; i=k; i++) {F[i]=i; set [i]. data=i; set [i]. tag=-1;} for (j=0; i=1; i=n; i++) { r = find ( min (n, d[i-1]) ); if (F[r]!=0){ J[j++]=i; m=find(F[r]-1); union (m, r); F[r]=F[m]; } } } 该算法的计算时间为O(nα(2n,n))≈O(n) 3.5 最优归并模式 已知两个已分类文件: (F1, L1), (F2, L2), 归并的时间复杂度为O(L1+L2). 确定将n个长度不同的已分类文件归并在一起的最优方法(时间复杂度最低). 60