装箱问题的近似解.ppt

装箱问题的近似解 一 FFD FirstFitStrategy 策略 Firstfitstrategy placesanobjectinthefirstbininwhichitfits FFDstrategyisamodificationthatsortstheobjectsfirstsothattheyareconsideredinorderofnon increasingsize 二 例 P573 三 算法13 1装箱问题 FFD binpackFFD S n bin float used newfloat n 1 inti j SortSintodescendingorder for i 1 i n i for j 1 j n j if used j si 1 0 bin i j used j si break 四 FFD算法的复杂性 O nlogn O n n 1 2 O n2 引理13 9 设S s1 s2 sn 为一个非递增序列 opt S 是S所需要的最小箱包数 则所有被FFD放入附加箱 下标 opt S 的object的大小至多为1 3 证明 证明 设i为第一个被FFD放入opt S 1的object的下标 要证明si 1 3 反证 设si 1 3 则s1 s2 si 1 3 则箱子Bj 0 j opt s 至多包含2个object 我们要证明存在k 0 k是第一个满足下列条件的箱子下标 它只含有1个s1 s2 si中的object 而余下的opt s k个箱子中包含2个object 反证 设存在箱子Bp Bq 其中p q Bp中含有2个s1 s2 si中的object 分别为t和u 其中t u 而Bq中仅有1个object 为v 因为S是非递减序列 所以t v u si 综合这2点 可以得出1 t u v si 则FFD就会把第i个object放在箱子Bq中 与i opt s 矛盾 所以存在k 0 k是第一个满足只含有1个object 而余下的opt s k个箱子中包含2个object的箱子下标 在最优解的情况下 所有object都会放置在opt s 个箱子中 不失一般性 我们假定前k个箱子不含有objectk 1 i 1 则在最优解的情况下 objectk 1 i 1 将会被放在Bk 1 Bopt 并且它们中的每一个都被放入2个object 于是 第i个object被放置在前面的那个箱子呢 因为它的size 1 3 所以放置在前面的那1箱子都不合适 利用 最优 情况导出矛盾 引理13 10 对任意输入S s1 s2 sn FFD放在附加箱子的object个数至多为opt s 1 证明 因为 在最优情况下 每个箱子的容量为1箱子的个数为opt s 反证 设FFD把opt S 个objects放入附加箱 它们的大小分别为t1 t2 topt s 用bj表示箱子Bj的最后容量 1 j opt s 如果bj ti 1 则FFD就可以把ti放入Bj中 但现在FFD把ti放入opt s 以后的桶中了 所以产生了下列矛盾的表达式 定理13 11 RFFD m 4 3 1 3m 无限的情况下 SFFD m 3 2R和S的意义参见P572页 证明 设输入序列为 s1 s2 sn opt S m 则FFD放在附加箱子的obj