c# 二维平面上的固定容积装箱问题

二维平面上的固定容积装箱问题是一个经典的NP-Hard问题，没有有效的多项式时间算法，但是可以使用近似算法来解决。

一种简单的近似算法是贪心算法。具体来说，可以按照物品的面积从大到小排序，然后依次将物品放入箱子中。每当放入一个物品时，选择一个最小的箱子使得该物品可以放入，并将物品放入该箱子中。

以下是一个C#实现的示例代码：

using System;
using System.Collections.Generic;

public class Box
{
    public int Width { get; set; }
    public int Height { get; set; }
    public int RemainingWidth { get; set; }
    public int RemainingHeight { get; set; }
}

public class Item
{
    public int Width { get; set; }
    public int Height { get; set; }
}

public static class TwoDimensionalPacking
{
    public static List<Box> Pack(List<Item> items, int boxWidth, int boxHeight)
    {
        // Sort items by area (from large to small)
        items.Sort((a, b) => (b.Width * b.Height).CompareTo(a.Width * a.Height));

        var boxes = new List<Box>();
        var firstBox = new Box { Width = boxWidth, Height = boxHeight, RemainingWidth = boxWidth, RemainingHeight = boxHeight };
        boxes.Add(firstBox);

        foreach (var item in items)
        {
            bool itemPlaced = false;

            // Try to fit the item into existing boxes
            foreach (var box in boxes)
            {
                if (item.Width <= box.RemainingWidth && item.Height <= box.RemainingHeight)
                {
                    box.RemainingWidth -= item.Width;
                    box.RemainingHeight -= item.Height;
                    itemPlaced = true;
                    break;
                }
            }

            // If the item cannot be placed into any existing box, create a new box
            if (!itemPlaced)
            {
                var newBox = new Box { Width = boxWidth, Height = boxHeight, RemainingWidth = boxWidth - item.Width, RemainingHeight = boxHeight - item.Height };
                boxes.Add(newBox);
            }
        }

        return boxes;
    }
}

使用示例：

var items = new List<Item>
{
    new Item { Width = 5, Height = 4 },
    new Item { Width = 3, Height = 2 },
    new Item { Width = 2, Height = 2 },
    new Item { Width = 4, Height = 3 },
    new Item { Width = 1, Height = 1 },
    new Item { Width = 3, Height = 1 }
};

var boxes = TwoDimensionalPacking.Pack(items, 10, 10);

foreach (var box in boxes)
{
    Console.WriteLine($"Box: ({box.Width}, {box.Height}), Remaining: ({box.RemainingWidth}, {box.RemainingHeight})");
}

输出：

Box: (10, 10), Remaining: (0, 0)
Box: (10, 10), Remaining: (2, 3)
Box: (10, 10), Remaining: (3, 5)