二维矩形装箱问题 python

二维矩形装箱问题是一个经典的优化问题，其目标是将一组不同大小的矩形尽可能紧密地放入一个矩形容器中，以最小化容器的面积或者最大化利用率。这个问题在物流、制造业和计算机图形学等领域都有广泛的应用。

在Python中，可以使用不同的算法来解决二维矩形装箱问题。其中一种常见的算法是基于贪心策略的最佳适应算法。该算法的基本思想是按照矩形的面积从大到小的顺序依次将矩形放入容器中，每次选择一个最合适的位置进行放置。

以下是一个简单的Python代码示例，演示了如何使用最佳适应算法解决二维矩形装箱问题：

class Rectangle:
    def __init__(self, width, height):
        self.width = width
        self.height = height

def pack_rectangles(rectangles, container_width, container_height):
    container = [[0, 0, container_width, container_height]]  # 初始容器
    packed_rectangles = []

    for rectangle in rectangles:
        best_index = -1
        best_fit = float('inf')

        for i, (x, y, width, height) in enumerate(container):
            if rectangle.width <= width and rectangle.height <= height:
                fit = max(width - rectangle.width, height - rectangle.height)
                if fit < best_fit:
                    best_fit = fit
                    best_index = i

        if best_index == -1:
            # 创建新的容器
            container.append([0, 0, container_width, container_height])
            best_index = len(container) - 1

        x, y, width, height = container[best_index]
        packed_rectangles.append((rectangle, x, y))
        
        # 更新容器
        if rectangle.width == width and rectangle.height == height:
            del container[best_index]
        elif rectangle.width == width:
            container[best_index] = [x, y + rectangle.height, width, height - rectangle.height]
        elif rectangle.height == height:
            container[best_index] = [x + rectangle.width, y, width - rectangle.width, height]
        else:
            container.append([x + rectangle.width, y, width - rectangle.width, rectangle.height])
            container[best_index] = [x, y + rectangle.height, width, height - rectangle.height]

    return packed_rectangles

# 示例用法
rectangles = [Rectangle(4, 5), Rectangle(3, 6), Rectangle(2, 7), Rectangle(3, 4)]
container_width = 10
container_height = 10

packed_rectangles = pack_rectangles(rectangles, container_width, container_height)

for rectangle, x, y in packed_rectangles:
    print(f"Rectangle ({rectangle.width}, {rectangle.height}) is placed at ({x}, {y})")

这段代码使用了一个`Rectangle`类来表示矩形，`pack_rectangles`函数接受一个矩形列表、容器的宽度和高度作为输入，并返回一个包含每个矩形及其在容器中位置的列表。在示例用法中，我们创建了一个矩形列表，并将其放入一个10x10的容器中，然后打印出每个矩形的位置信息。