### 二维矩形条带装箱算法简介 二维矩形条带装箱问题（Strip Packing Problem, SPP）是一个经典的组合优化问题，目标是将一组给定大小的矩形放入一个宽度固定、高度可变的条带中，使得条带的高度最小化。这是一个NP难问题[^1]，因此通常采用启发式或元启发式算法来求解近似最优解。 以下是一个基于简单的“先下后左”（Bottom-Left）策略的Python实现，该策略试图将每个矩形放置在当前条带中的最低位置，并尽可能靠左[^2]。 ### Python 实现代码 ```python class Rectangle: def __init__(self, width, height): self.width = width self.height = height self.x = 0 self.y = 0 def place_rectangle(rectangles, strip_width): rectangles = sorted(rectangles, key=lambda r: -r.width * r.height) # 按面积降序排列 placed_rectangles = [] max_height = 0 for rect in rectangles: best_y = float('inf') best_x = float('inf') # 遍历已放置的矩形，寻找最佳位置 for placed in placed_rectangles: if placed.x + placed.width <= strip_width and placed.y + placed.height < best_y: best_y = placed.y + placed.height best_x = placed.x if placed.y + placed.height <= max_height and placed.x + placed.width < best_x: best_y = placed.y best_x = placed.x + placed.width # 如果没有找到合适的位置，则放置在顶部 if best_y == float('inf'): best_y = max_height best_x = 0 # 更新矩形位置 rect.x = best_x rect.y = best_y placed_rectangles.append(rect) # 更新最大高度 max_height = max(max_height, rect.y + rect.height) return max_height, placed_rectangles # 示例使用 rectangles = [Rectangle(4, 5), Rectangle(6, 3), Rectangle(2, 7), Rectangle(5, 4)] strip_width = 10 height, placed = place_rectangle(rectangles, strip_width) print(f"Minimum height: {height}") for i, rect in enumerate(placed): print(f"Rectangle {i}: (x={rect.x}, y={rect.y})") ``` ### 算法说明 上述代码实现了一个简单的贪心算法，通过按面积排序矩形并尝试将其放置在最低且最左侧的位置来减少条带高度。这种方法虽然不是最优解，但在许多情况下能够提供较好的近似结果[^3]。 ### 进一步改进 为了获得更优的结果，可以考虑以下方法： 1. 使用遗传算法（Genetic Algorithm, GA）或模拟退火（Simulated Annealing, SA）等元启发式算法。 2. 引入旋转功能，允许矩形以不同方向放置。 3. 应用动态规划技术，在小规模问题中求解精确解。