堆积木算法问题
若干100*100的盒子。和自定义数量和边长的积木，积木的大小不一定，如18*12，32*90
现在输入一定数量的积木，和每个积木的大小。（从键盘输入，用TXT文本保存信息）把这些积木放入盒子中，要求使用的盒子尽可能的少，并且这个算法要尽可能的快。
最后 在TXT输出 使用的盒子的数量，和每个盒子中积木的大小和位置。
可能有人弄不懂这个题目的意思，我简单解释一下，就是现在把一些自定义数量和大小的小矩形放入100*100的大矩形，要求使用的大矩形尽量少，并且输出每个大矩形内小矩形的数量，和每个小矩形的大小和坐标。
求如何在盒子中摆放积木算法。
[解决办法]
写了一个挨个放的，LZ可以自行修改一下，不是求最优，甚至算不上什么近似算法，只是一个思路。
仅作参考。由于不是求最优，因此效率都没有仔细考虑，仅仅是能够运行。
using System;
using System.Collections.Generic;
using System.Drawing;
namespace csdnTest
{
class SizeAndCount : IComparable <SizeAndCount>
{
public Size RectSize;
public int RectCount;
public SizeAndCount(Size size, int count)
{
if (size.Height > size.Width)
RectSize = Rotate(size);
else
RectSize = size;
RectCount = count;
}
public int CompareTo(SizeAndCount other)
{
return (RectSize.Height * RectSize.Width).CompareTo(other.RectSize.Height * other.RectSize.Width) * -1;
}
public static Size Rotate(Size x)
{
return new Size(x.Height, x.Width);
}
}
class Program
{
//盒子大小
static Size MSize = new Size(100, 100);
static bool[,] Matrix;
//所有矩形的大小和数量
static List <SizeAndCount> Items = new List <SizeAndCount>();
static void Main(string[] args)
{
//添加一些物品
Items.Add(new SizeAndCount(new Size(10, 20), 15));
Items.Add(new SizeAndCount(new Size(15, 15), 8));
Items.Add(new SizeAndCount(new Size(20, 90), 30));
Items.Add(new SizeAndCount(new Size(12, 18), 5));
Items.Add(new SizeAndCount(new Size(15, 18), 5));
//按面积排个序
Items.Sort();
int count = 0;
while (!ItemsCheck())
{
Matrix = new bool[MSize.Width, MSize.Height];
Counter(0);
count++;
}
Console.WriteLine("需要{0}个盒子", count);
Console.ReadKey();
}
static bool ItemsCheck()
{
foreach (SizeAndCount item in Items)
if (item.RectCount > 0)
return false;
return true;
}
static void Counter(int currentIndex)
{
if (currentIndex == Items.Count)
return;
if (Items[currentIndex].RectCount == 0)
{
Counter(currentIndex + 1);
return;
}
Point[] points = GetAvailablePoints();
foreach (Point p in points)
{
Rectangle r1 = new Rectangle(p, Items[currentIndex].RectSize);
Rectangle r2 = new Rectangle(p, SizeAndCount.Rotate(Items[currentIndex].RectSize));
if (CheckRectangle(r1))
{
SetRectangle(r1, true);
Items[currentIndex].RectCount--;
Counter(currentIndex);
break;
}
if (CheckRectangle(r2))
{
SetRectangle(r2, true);
Items[currentIndex].RectCount--;
Counter(currentIndex);
break;
}
}
Counter(currentIndex + 1);
}
static Point[] GetAvailablePoints()
{
List <Point> points = new List <Point>();
for (int i = 0; i < MSize.Width; i++)
{
for (int j = 0; j < MSize.Height; j++)
{
Point po = new Point(i,j);
if (IsAvailable(po))
points.Add(po);
}
}
return points.ToArray();
}
static bool IsAvailable(Point point)
{
if(Matrix[point.X, point.Y])
return false;
if (point.X > 0 && !Matrix[point.X - 1, point.Y])
return false;
if (point.Y > 0 && !Matrix[point.X, point.Y - 1])
return false;
if (point.X < MSize.Width - 1 && Matrix[point.X + 1, point.Y])
return false;
if (point.Y < MSize.Height - 1 && Matrix[point.X, point.Y + 1])
return false;
return true;
}
static void SetRectangle(Rectangle rect, bool value)
{
for (int i = rect.X; i < rect.X + rect.Size.Width; i++)
for (int j = rect.Y; j < rect.Y + rect.Size.Height; j++)
Matrix[i, j] = value;
}
static bool CheckRectangle(Rectangle rect)
{
for (int i = rect.X; i < rect.X + rect.Size.Width; i++)
for (int j = rect.Y; j < rect.Y + rect.Size.Height; j++)
if (i >= MSize.Width || j >= MSize.Height || Matrix[i, j]) return false;
return true;
}
}
}
