请用C#编写二维装箱问题,程序不要用Tuple元组,并给出详细注释
时间: 2024-02-16 20:03:09 浏览: 20
好的,以下是使用C#编写的二维装箱问题程序,注释已经加上:
```csharp
using System;
using System.Collections.Generic;
using System.Linq;
namespace BinPacking
{
class Program
{
static void Main(string[] args)
{
// 测试数据
int binWidth = 6;
int binHeight = 4;
List<Box> boxes = new List<Box>()
{
new Box(3, 2),
new Box(1, 1),
new Box(2, 4),
new Box(1, 2),
new Box(3, 1)
};
// 调用装箱函数
var packedBoxes = PackBoxes(binWidth, binHeight, boxes);
// 输出结果
Console.WriteLine($"Bin size: {binWidth} x {binHeight}");
Console.WriteLine($"Total boxes: {boxes.Count}");
Console.WriteLine($"Packed boxes: {packedBoxes.Count}");
Console.WriteLine("Box positions:");
foreach (var box in packedBoxes)
{
Console.WriteLine($"Box ({box.Width} x {box.Height}): ({box.X}, {box.Y})");
}
}
// 装箱函数
static List<Box> PackBoxes(int binWidth, int binHeight, List<Box> boxes)
{
// 对所有箱子按面积从大到小排序
boxes = boxes.OrderByDescending(b => b.Area).ToList();
// 初始化一个空白的矩形,代表装箱空间
Rectangle bin = new Rectangle(0, 0, binWidth, binHeight);
// 初始化已放置箱子的列表
List<Box> packedBoxes = new List<Box>();
// 遍历每个箱子
foreach (var box in boxes)
{
// 尝试将箱子放置在空白矩形中
var packedBox = PackBoxInRectangle(box, bin);
// 如果箱子放置成功,则将其加入已放置箱子列表中
if (packedBox != null)
{
packedBoxes.Add(packedBox);
}
}
return packedBoxes;
}
// 在给定矩形中放置箱子
static Box PackBoxInRectangle(Box box, Rectangle rect)
{
// 如果箱子无法放入矩形,则返回空
if (box.Width > rect.Width || box.Height > rect.Height)
{
return null;
}
// 将箱子放置在矩形的左上角
Box packedBox = new Box(box.Width, box.Height);
packedBox.X = rect.X;
packedBox.Y = rect.Y;
// 更新矩形,将已放置的箱子所占用的位置从矩形中删除
int newX = rect.X + box.Width;
int newY = rect.Y + box.Height;
int newWidth = rect.Width - box.Width;
int newHeight = rect.Height - box.Height;
// 如果剩余空间在水平方向上大于垂直方向,则将剩余空间分成两个矩形,一个在箱子的右侧,一个在箱子的下方
if (newWidth > newHeight)
{
Rectangle rightRect = new Rectangle(newX, rect.Y, newWidth, box.Height);
Rectangle bottomRect = new Rectangle(rect.X, newY, rect.Width, newHeight);
// 尝试先将箱子放在右侧矩形中,如果无法放置,则放在下方矩形中
Box rightPackedBox = PackBoxInRectangle(box, rightRect);
if (rightPackedBox != null)
{
return packedBox;
}
else
{
Box bottomPackedBox = PackBoxInRectangle(box, bottomRect);
if (bottomPackedBox != null)
{
return packedBox;
}
}
}
// 如果剩余空间在垂直方向上大于水平方向,则将剩余空间分成两个矩形,一个在箱子的下方,一个在箱子的右侧
else
{
Rectangle bottomRect = new Rectangle(rect.X, newY, rect.Width, newHeight);
Rectangle rightRect = new Rectangle(newX, rect.Y, newWidth, rect.Height);
// 尝试先将箱子放在下方矩形中,如果无法放置,则放在右侧矩形中
Box bottomPackedBox = PackBoxInRectangle(box, bottomRect);
if (bottomPackedBox != null)
{
return packedBox;
}
else
{
Box rightPackedBox = PackBoxInRectangle(box, rightRect);
if (rightPackedBox != null)
{
return packedBox;
}
}
}
// 如果无法放置箱子,则返回空
return null;
}
}
// 表示一个矩形
class Rectangle
{
public int X { get; set; }
public int Y { get; set; }
public int Width { get; set; }
public int Height { get; set; }
public Rectangle(int x, int y, int width, int height)
{
X = x;
Y = y;
Width = width;
Height = height;
}
}
// 表示一个箱子
class Box
{
public int Width { get; set; }
public int Height { get; set; }
public int X { get; set; }
public int Y { get; set; }
public int Area { get { return Width * Height; } }
public Box(int width, int height)
{
Width = width;
Height = height;
}
}
}
```