Bin-Packing Algorithms | 装箱算法

📚 Bin-Packing Algorithms | 装箱算法

Bin-packing algorithms are decision-making procedures for a classic optimisation problem: given items of known sizes and bins of fixed capacity, pack all items using as few bins as possible. In the Edexcel A Level Computer Science specification you are expected to trace and compare three main heuristic strategies: first-fit, first-fit decreasing and full-bin packing.

装箱算法是解决经典优化问题的决策过程：给定已知大小的物品和固定容量的箱子，用尽可能少的箱子装下所有物品。在Edexcel A Level计算机科学大纲中，你需要跟踪并比较三种主要启发式策略：首次适应、降序首次适应和满箱策略。

1. Problem Definition and Terminology | 问题定义与术语

In a bin-packing problem every item has a size, and every bin has the same capacity. The total size of items placed in a bin must not exceed the bin capacity. The objective is to minimise the number of bins used.

在装箱问题中，每个物品都有大小，每个箱子容量相同。放入同一箱子的物品总大小不能超过箱子容量。目标是最小化使用的箱子数量。

An important lower bound is calculated by dividing the total size of all items by the bin capacity and rounding up. This gives the theoretical minimum number of bins if all space could be used perfectly.

一个重要下界是将所有物品总大小除以箱子容量并向上取整。这给出了如果所有空间都能被完美利用时的理论最少箱子数。

Lower bound = ⌈ total item size ÷ bin capacity ⌉

2. Why Exact Solutions Are Hard | 为什么精确解很难

Bin packing is NP-hard, meaning that no known algorithm can always find the optimal solution quickly for large numbers of items. The number of possible groupings grows extremely fast, so exhaustive search becomes impractical.

装箱问题是NP难问题，这意味着对于大量物品，目前没有已知算法能始终快速找到最优解。可能的分组数量增长极快，因此穷举搜索变得不现实。

Heuristics trade optimality for speed: they produce a good, traceable solution in a small number of steps, even though they may use more bins than necessary.

启发式方法用最优性换取速度：它们用少量步骤产生一个良好的、可跟踪的解，尽管可能使用比必要数量更多的箱子。

3. First-Fit Algorithm | 首次适应算法

The first-fit algorithm processes items in their given order. Each item is placed into the first bin that has enough remaining capacity. If no existing bin can hold the item, a new bin is opened.

首次适应算法按给定顺序处理物品。每个物品被放入第一个有足够剩余容量的箱子中。如果没有现有箱子能装下该物品，则打开一个新箱子。

Example: bin capacity 10, items in order 2, 5, 4, 7, 1, 3, 8. First-fit produces the following allocation:

示例：箱子容量为10，物品顺序为2、5、4、7、1、3、8。首次适应算法产生如下分配：

This uses

Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）