13装箱问题 131装箱问题及其串行算法 经典的一维装箱问题( Bin Packing Problem)是指,给定n件物品的序列 Ln=<a1,a2…,an>,物品a;(1≤i≤n)的大小s(a1)∈(0.1,要求将这些物品装入单位容 量1的箱子B1,B2…,Bn中,使得每个箱子中的物品大小之和不超过1,并使所使用的箱子 数目m最小。 下次适应算法( Next Fit Algorithm)是最早提出的、最简单的一个在线算法,[Joh73 首次仔细分析了下次适应算法的最坏情况性能。下次适应算法维持一个当前打开的箱子,它 依序处理输入物品,当物品到达时检查该物品能否放入这个当前打开的箱子中,若能则放入: 否则把物品放入一个新的箱子中,并把这个新箱子作为当前打开的箱子。算法描述如下: 算法16.5装箱问题的下次适应算法 输入:输入物品序列L=<a12a2,…,an>。 输出:使用的箱子数目m,各装入物品的箱子P=<B1,B2,…,Bn> procedure NextFit Begin (1)S(B)=1/初始化当前打开的箱子B,令B已满* (2)m=0 /*使用箱子计数 (3)fori=1 to n do ifs(ai)+s(B)s I then (i)s(B)=s(B)+sa)/*把a放入B中 (i)m=m+1 /*使用的箱子数加一*/ (ii)b=Bm /*新打开箱子Bm*/ (iii)s(B)=s(ai) /*把a放入B中 end if End / NextFit * 132装箱问题的并行算法 算法16.5使用一遍扫描物品序列来实现,本身具有固有的顺序性,其时间复杂度为On)。 我们使用平衡树和倍增技术对其进行并行化。首先利用前缀和算法建立一个链表簇,令A7 为输入物品序列中第i件物品的大小,如果链表指针由AD指向Ak,则表示 AD+4+1]+.+4k>1且A++1]++A/k-1]≤1;其后利用倍增技术计算以4①]为头的 链表的长度,而以A(1)为头的链表的长度即是下次适应算法所使用的箱子数目。接下来利用 在上一步骤中产生的中间数据反向建立一棵二叉树,使该二叉树的叶节点恰好是下次适应算 法在各箱子中放入的第一个物品的序号:最后,根据各箱子中放入的第一个物品的序号,使 66 1.3 装箱问题 1.3.1 装箱问题及其串行算法 经典的一维 装 箱 问 题 (Bin Packing Problem) 是指，给定 n 件物品的序列 1 2 , , , L a a a n n =  ，物品 a (1 i n) i   的大小 ( )(0,1] ai s ，要求将这些物品装入单位容 量 1 的箱子 1 2 , , , B B B m 中，使得每个箱子中的物品大小之和不超过 1，并使所使用的箱子 数目 m 最小。 下次适应算法（Next Fit Algorithm）是最早提出的、最简单的一个在线算法，[Joh73] 首次仔细分析了下次适应算法的最坏情况性能。下次适应算法维持一个当前打开的箱子，它 依序处理输入物品，当物品到达时检查该物品能否放入这个当前打开的箱子中，若能则放入； 否则把物品放入一个新的箱子中，并把这个新箱子作为当前打开的箱子。算法描述如下： 算法 16.5 装箱问题的下次适应算法 输入：输入物品序列 1 2 , , , L a a a =  n 。 输出：使用的箱子数目 m，各装入物品的箱子 1 2 , , , P B B B =  m 。 procedure NextFit Begin （1）s(B) = 1 /* 初始化当前打开的箱子 B，令 B 已满 */ （2）m = 0 /* 使用箱子计数 */ （3）for i = 1 to n do if s(ai) + s(B)  1 then （i） s(B) = s(B) + s(ai) /* 把 ai 放入 B 中 */ else （i） m = m + 1 /* 使用的箱子数加一 */ （ii） B = Bm /* 新打开箱子 Bm */ （iii）s(B) = s(ai) /* 把 ai 放入 B 中 */ end if end for End /* NextFit */ 1.3.2 装箱问题的并行算法 算法 16.5 使用一遍扫描物品序列来实现，本身具有固有的顺序性，其时间复杂度为 O(n)。 我们使用平衡树和倍增技术对其进行并行化。首先利用前缀和算法建立一个链表簇，令 A[i] 为 输 入 物 品 序列 中 第 i 件物品的大小, 如 果链 表 指 针由 A[j] 指 向 A[k] ，则表示 A[j]+A[j+1]+…+A[k]>1 且 A[j]+A[j+1]+…+A[k-1]1；其后利用倍增技术计算以 A[1]为头的 链表的长度，而以 A(1)为头的链表的长度即是下次适应算法所使用的箱子数目。接下来利用 在上一步骤中产生的中间数据反向建立一棵二叉树，使该二叉树的叶节点恰好是下次适应算 法在各箱子中放入的第一个物品的序号；最后，根据各箱子中放入的第一个物品的序号，使