用二分法确定各物品所放入的箱子的序号。 算法166并行下次适应算法 输入:数组An],其中4[为输入物品序列中第i个物品的大小。 输出:使用的箱子数目m,每个物品应放入的箱子序号数组B[n procedure PNext Fit (1)调用求前缀和的并行算法计算FUj}=A[1+A[2H+…+4[ (2) forj=I to n pardo 借助F,使用二分法计算C[0j=max{4U]+4计+1]+…+4(k]≤1} nd fe /*以下(3)-(8),计算下次适应算法使用的箱子数目m (3)C[0,n+1=n (4)h=0 (5) for j=l to n pardo E[, J=l end for (6) while Cth,1]≠nd (6.1)h=h+1 (6.2)forj=I to n pardo if CTh-1,J]=n then (i) E[h,j]=E[h-1,j1 (ii)C[,j]=CTh-1j1 (i)E[h,j=E[h-1,j+E[h-1,Ch-1,j+1 (i1)Ch,j=CTh-1, Ch-1,J+1] d if end for end while (7) height=h (9)/计算D[O,j=第j个箱子中第一件物品在输入序列中的编号* for h= height downto o do forj=1 to n/2 pardo (i) ifj=even then D[h j]=C[h, D[h-1,j/2J]+1 endif (ii) ifj=I then D[h, 1]=1 endif (iii) ifj=odd>I then D[h, j]=D[h-1, [j+1)/2]endif end for (10) for F=l to n pardo/*计算B[=第j个物品所放入的箱子序号* 使用二分法计算B]=max{kD0k],D[Ok+1或者k=m} end for End/* PNext Fit*/ MPI源程序请参见所附光盘。7 用二分法确定各物品所放入的箱子的序号。 算法 16.6 并行下次适应算法 输入：数组 A[1,n]，其中 A[i]为输入物品序列中第 i 个物品的大小。 输出：使用的箱子数目 m，每个物品应放入的箱子序号数组 B[1,n]。 procedure PNextFit Begin （1）调用求前缀和的并行算法计算 F[j]= A[1]+A[2]+…+A[j] （2）for j = 1 to n pardo 借助 F[j]，使用二分法计算 C[0,j]= max{k|A[j]+A[j+1]+…+A[k] 1} end for /* 以下（3）-（8），计算下次适应算法使用的箱子数目 m */ （3）C[0, n+1] = n （4）h = 0 （5）for j=1 to n pardo E[0, j]=1 end for （6）while C[h,1]  n do （6.1）h = h + 1 （6.2）for j = 1 to n pardo if C[h - 1, j] = n then （i）E[h, j] = E[h-1, j] （ii）C[h,j] = C[h - 1,j] else （i）E[h, j] = E[h - 1, j] + E[h - 1,C[h - 1, j] + 1] （ii）C[h, j] = C[h - 1,C[h - 1, j] + 1] end if end for end while （7）height = h （8）m = E[height, 1] （9）/* 计算 D[0, j]=第 j 个箱子中第一件物品在输入序列中的编号 */ for h = height downto 0 do for j = 1 to n / 2 h pardo （i）if j = even then D[h,j] = C[h,D[h-1,j/2]]+1 endif （ii）if j = 1 then D[h,1] = 1 endif （iii）if j = odd > 1 then D[h,j] = D[h-1,[j+1]/2] endif end for end for （10）for j=1 to n pardo /* 计算 B[j] = 第 j 个物品所放入的箱子序号 */ 使用二分法计算 B[j] = max{ k | D[0,k] j , D[0,k+1] >j 或者 k = m } end for End /* PNextFit */ MPI 源程序请参见所附光盘