第八章 第八章 装箱问题 装箱问题 组合优化理论 组合优化理论 Combinatorial Optimization Theory第八章 装箱问题 1 1 装箱问题的描述 装箱问题的描述 2 2 装箱问题的最优解值下界 装箱问题的最优解值下界 3 3 装箱问题的近似算法 装箱问题的近似算法第八章 第八章 装箱问题 装箱问题 装箱问题（Bin Packing）是一个经典的组合优化 问题，有着广泛的应用，在日常生活中也屡见不鲜 . 1 1 装箱问题的描述 装箱问题的描述 设有许多具有同样结构和负荷的箱子 B 1 ，B 2 ， 其数量足够供所达到目的之用 . 每个箱子的负荷（可为 长度、重量 etc.）为 C ,今有 n 个负荷为 w j ，0 w j C j = 1，2，n 的物品 J 1 ，J 2 ，J n 需要装入箱内. 装箱问题： 装箱问题： 是指寻找一种方法，使得能以最小数量的箱子数将 J 1 ，J 2 ，J n 全部装入箱内 . .1 装箱问题的描述 由于 w i C，所以 BP 的最优解的箱子数不超过 n . . 设 箱子 B i 被使用 否则 物品 J j 放入箱子 B i
