用C# 写一个矩形套料的算法

矩形套料算法，也称为矩形排样算法，是一种常见的计算机优化问题，其目的是在给定的有限区域内尽可能多地放置矩形，以最小化浪费的面积和数量。

下面是一个用 C# 实现的基于贪心算法的矩形套料算法的示例：

using System;
using System.Collections.Generic;
using System.Linq;

namespace RectanglePacking
{
    class Rectangle
    {
        public int Width { get; set; }
        public int Height { get; set; }
        public int X { get; set; }
        public int Y { get; set; }
    }

    class RectanglePacking
    {
        static void Main(string[] args)
        {
            List<Rectangle> rectangles = new List<Rectangle>();
            rectangles.Add(new Rectangle { Width = 200, Height = 100 });
            rectangles.Add(new Rectangle { Width = 100, Height = 50 });
            rectangles.Add(new Rectangle { Width = 150, Height = 75 });
            rectangles.Add(new Rectangle { Width = 80, Height = 60 });
            rectangles.Add(new Rectangle { Width = 120, Height = 90 });

            int containerWidth = 500;
            int containerHeight = 300;

            List<Rectangle> packedRectangles = PackRectangles(rectangles, containerWidth, containerHeight);

            Console.WriteLine($"Total packed rectangles: {packedRectangles.Count}");
            foreach (Rectangle rectangle in packedRectangles)
            {
                Console.WriteLine($"Rectangle: ({rectangle.X}, {rectangle.Y}) - ({rectangle.X + rectangle.Width}, {rectangle.Y + rectangle.Height})");
            }
        }

        static List<Rectangle> PackRectangles(List<Rectangle> rectangles, int containerWidth, int containerHeight)
        {
            List<Rectangle> packedRectangles = new List<Rectangle>();

            rectangles = rectangles.OrderByDescending(r => r.Width).ToList();

            foreach (Rectangle rectangle in rectangles)
            {
                bool isPacked = false;

                for (int y = 0; y < containerHeight - rectangle.Height + 1; y++)
                {
                    for (int x = 0; x < containerWidth - rectangle.Width + 1; x++)
                    {
                        rectangle.X = x;
                        rectangle.Y = y;

                        if (!IsOverlapping(rectangle, packedRectangles))
                        {
                            packedRectangles.Add(rectangle);
                            isPacked = true;
                            break;
                        }
                    }

                    if (isPacked)
                    {
                        break;
                    }
                }
            }

            return packedRectangles;
        }

        static bool IsOverlapping(Rectangle rectangle, List<Rectangle> rectangles)
        {
            foreach (Rectangle r in rectangles)
            {
                if (rectangle.X + rectangle.Width > r.X && rectangle.X < r.X + r.Width && rectangle.Y + rectangle.Height > r.Y && rectangle.Y < r.Y + r.Height)
                {
                    return true;
                }
            }

            return false;
        }
    }
}

在上面的示例中，我们定义了一个 `Rectangle` 类来表示矩形，其中包含了宽度、高度、X 坐标和 Y 坐标等属性。然后，我们实现了一个 `PackRectangles` 方法来套矩形，并返回套好的矩形列表。在这个方法中，我们采用了贪心算法的思想，将矩形按宽度从大到小排序，然后依次将每个矩形与已经套好的矩形进行比较，找到一个不与已经套好的矩形重叠的位置，并将该矩形放置在此位置上。如果找不到合适的位置，则跳过该矩形。最后，返回套好的矩形列表。

在上面的示例中，我们定义了一个简单的矩形列表，并且定义了一个大小为 500x300 的容器。然后，我们调用了 `PackRectangles` 方法，并将矩形列表和容器大小作为参数传入。最后，输出套好的矩形列表中每个矩形的位置和大小。