【摘要】 给定物品系列,要求将所有物品装入到不同类型的箱子中,以实现从第1个箱子到最后1个箱子被使用的箱子的总尺寸最小化.用最坏情况绝对性能研究在线算法,给出了一种最坏情况绝对性能比是3的近似算法.作为这种算法的应用,给出了一种脱线算法,其最坏情况绝对性能比是2.更多还原

【Abstract】 For a list of given items,how to pack them into a list of variable-sized bins in sequence so as to minimize the total size of bins ranging from the first one to the last one.The on-line algorithms is studied in terms of the absolute worst-case ratio.A simple on-line algorithm is shown to have an absolute worst-case ratio of 3.Also,we present a very simple off-line algorithm by applying the algorithm to a sorted list of items.It proves that the absolute worst-case ratio is 2.更多还原