装箱问题和排序问题 1 1本讲主要内容装箱问题（Bin Packing）最小完工时间安排（排序问题）（Minimum Makespan Scheduling)2 2Bin Packing装箱问题：给定n个物件，大小为 用单位体积的箱子来装这些物件，找一个装箱方案使得所用的箱子数目最少？通俗地说，把 分成最少的组数，使得每组数的和不超过1。在工业中有许多应用，譬如在下料问题中，箱子代表标准木料的长度，而 表示实际问题中需要裁截成的木料长度。当然，需要的标准料越少越好。3 3一个2倍近似算法4 4证明5 5一个不可逼近性结果6 67 78 8NP-难问题按照其可逼近性分类没有常数倍近似比：Set-Cover，TSP，Maximum Independent Set,有常数倍近似比但不能任意接近1：Vertex-Cover，Bin Packing,近似比可以为1+（任意逼近1）。Knapsack，Scheduling.9 9多项式时间近似方案（Polynomial Time Approximation Scheme,PTAS),渐近多项式时间近似方案1010一个渐进的PTAS1111限制装箱问
