[Решено]Оптимальное заполнение площади.[Алгоритм][C#]

Есть площадь определённого размера XY.
Имеется определённое кол-во N элементов с неизвестными размерами AB. (все элементы одинаковы.)

Задача найти AB так, что-бы площадь была оптимально заполнена элементами. Тоесть как можно меньше свободного места оставалось на площади. Елементы не должны выходить за границы площади.

Некую роль здесь играет ориентация расположения. Для примера возьмём горизонтальную. Расположение решёткой.

Вроде бы ничего не забыл. Если что - спрашивайте.
Надеюсь на вашу помощь.

 

Если всё площади и фигуры имеют прямоугольную форму, то
1) S1 = X * Y; - узнаешь площадь общую
2) S2 = целое(S1 / N); - узнаешь максимальный размер площади фигуры
3) Далее надо решить систему уровнений типа

а) A*B стремится к S2
б) A * Z1 стремится к X
в) B * Z2 стремится к Y
г) Z1 * Z2 стремится к N

По правилам - система может быть решена если кол-во неизвестных = кол-во уравнений. так что скорее всего норм будет.

Самая сложность в решении, что значение должно стремиться к нужному числу, по этому надо тока перебором

 

Спасибо Слешик. Чтото подобное у меня тоже получилось, но меня смутил перебор. Так как это явно математическая задача, надеялся, что существует готовый упрощённый алгоритм. Весь гугл перекопал, но ничего не нашёл, т.к. точно не знаю, по каким ключевым словам искать.

Ну что-ж придётся решать так.

 

Интересно

Не по поводу твоей задачи, однако, тема довольно интересно, о размещении максимального количества предметов на определённой площаде(в определённом обьеме),
а хабре мелькал интересный Тыц .
Статья довольно познавательная, возможно решение пригодиться в дальнейшем.

ЗЫ, обрати внимание на коммент el777 и прилагаемую ссылку.

 

Всем спасибо!

Зделал так. (элементы в форме квадрата)
Код комментировать некогда, сорри.

Code:

private void ReorderElements()
{
	int controlCount = this.Controls.Count;
	if (controlCount < 1)
		return;

	int approxElementArea = (this.Width * this.Height) / controlCount;
	int approxElementSide = (int)Math.Sqrt(approxElementArea);

	while (this.ElementCount(approxElementSide) < controlCount)
	{
		approxElementSide--;
	}

	Size еlementItemSize = new Size(approxElementSide, approxElementSide);
	Point[] elementPosition = this.CalculateElementPositions(
                          approxElementSide, this.rowCount, this.columnCount);

	for (int i = 0; i<controlCount; i++)
	{
		this.Controls[i].Size = elementItemSize;
		this.Controls[i].Location = elementPosition[i];
	}
}

Code:

private int ElementCount(int approxElementSide)
{
	columnCount = this.Width / approxElementSide;
	rowCount = this.Height / approxElementSide;

	return columnCount*rowCount;
}

Code:

private Point[] CalculateElementPositions(int approxElementSide, int rowCount, int columnCount)
{
	Point[] elementPoints = new Point[columnCount * rowCount];
	int x = 0, y = 0, k = 0;

	if (verticalElementOrientation)
	{
		for (int cols = 0; cols < columnCount; cols++)
		{
			y = 0;
			for (int rows = 0; rows < rowCount; rows++)
			{
				еlementPoints[k++] = new Point(x, y);
				y += approxElementSide;
			}
			x += approxElementSide;
		}
	}

	else
	{
		for (int rows = 0; rows < rowCount; rows++)
		{
			x = 0;
			for (int cols = 0; cols < columnCount; cols++)
			{
				еlementPoints[k++] = new Point(x, y);
				x += approxElementSide;
			}
			y += approxElementSide;
		}
	}
	return elementPoints;
}