Разрезы без отходов

[Sheril]

Есть такая задача:
Разрезать прямоугольник размера X*Y на детали прямоугольной формы размера X1*Y1 и X2*Y2, чтобы отходы были минимальны. Возможны только вертикальные и горизонтальные разрезы. Т.е. после первого разреза получается два прямоугольника, которые в последствии также можно разрезать.
Входные данные
Входные данные находятся в текстовом файле с именем input.txt:
Во входном файле шесть целых чисел (1<=X<=100, 1<=Y<=100, 1<=X1<=X, 1<=Y1<=Y, 1<=X2<=X, 1<=Y2<=Y).

Выходные данные

Выходные данные должны быть записаны в текстовый файл с именем output.txt и иметь следующий формат:
единственное целое число равное минимальной сумме остатков.
Пример входных данных

10
10
2
9
3
4
Пример выходных данных
10

Подскажите, как написать максимально быстрый алгоритм?

[Carbon]

Куски на 90 градусов вращать можно?

[Sheril]

Да, детали вращать можно. И разрезы от края до края. Зигзагообразно резать нельзя. Эта задача как-то сводится к задаче о разрезке обоев с рисунком. Но как решать задачу про обои я знаю лишь в теории.

[raxp]

1- решение данной задачи представляет коммерческую ценность и немалую
2- существуют различные приближающие методы: генетические алгоритмы, симплекс-метод, параметрическая оптимизация, исключения интервалов и т.п. (это все есть в вики)
3- на форуме >>> обсуждалось <<<

тут очень хорошо расписан генетический алгоритм + прилагаю статью об еще одном методе фигурного раскроя (см. ниже)

[Carbon]

Сообщение от raxp

1- решение данной задачи представляет коммерческую ценность и немалую
2- существуют различные приближающие методы: генетические алгоритмы, симплекс-метод, параметрическая оптимизация, исключения интервалов и т.п. (это все есть в вики)
3- на форуме >>> обсуждалось <<<

тут очень хорошо расписан генетический алгоритм + прилагаю статью об еще одном методе фигурного раскроя (см. ниже)

Я тя умоляю. Там фигурный раскрой и вырезки наверняка произвольной формы. А тут вырезки всего двух вариантов и то они прямоугольные и раскрой от края до края.

Обычное динамическое программирование:

#include <stdio.h>


int main( int, char ** )
{

	int X, Y;
	int X1, Y1;
	int X2, Y2;

	scanf( "%d%d%d%d%d%d", &X, &Y, &X1, &Y1, &X2, &Y2 );
	
	int refuse[ 100 ][ 100 ];

	for ( int i = 0; i < X; ++i )
		for ( int j = 0; j < Y; ++j )
		{
			if ( i == X1 - 1 && j == Y1 - 1 ||
				i == Y1 - 1 && j == X1 - 1 ||
				i == X2 - 1 && j == Y2 - 1 ||
				i == Y2 - 1 && j == X2 - 1 )
				refuse[ i ][ j ] = 0;
			else
			{
				refuse[ i ][ j ] = ( i + 1 )*( j + 1 );

				int val = 1;

				for ( int k = 0, k_end = ( i + 1 ) >> 1; k < k_end && val; ++k )
				{
					val = refuse[ k ][ j ] + refuse[ i - 1 - k ][ j ];
					if ( refuse[ i ][ j ] > val ) refuse[ i ][ j ] = val;
				}

				for ( int k = 0, k_end = ( j + 1 ) >> 1; k < k_end && val; ++k )
				{
					val = refuse[ i ][ k ] + refuse[ i ][ j - 1 - k ];
					if ( refuse[ i ][ j ] > val ) refuse[ i ][ j ] = val;
				}
			}
		}

	printf( "%d", refuse[ X - 1 ][ Y - 1 ] );

	getchar();
	getchar();

	return 0;
}

[Sheril]

Carbon, Спасибо! Она работает очень(!) быстро. Вы сами придумали алгоритм или это уже существующий? Мы такого не учили... Хотелось бы почитать.
Нулями метим углы возможного расположения деталей. А как с помощью побитового сдвига(я надеюсь это он?) и оценок мы заполняем матрицу?

[Carbon]

Сообщение от Sheril

Carbon, Спасибо! Она работает очень(!) быстро. Вы сами придумали алгоритм или это уже существующий? Мы такого не учили... Хотелось бы почитать.
Нулями метим углы возможного расположения деталей. А как с помощью побитового сдвига(я надеюсь это он?) и оценок мы заполняем матрицу?

Я ж говорю. Это динамическое программирование.
Ну до этого я догадался сам, хотя подобную задачу видел на одной из школьных олимпиад.

Алгоритм такой:
Расчитываем все остатки при разрезании досок меньших размеров. По очереди рассматриваем все доски и пусть у нас встретилась доска PxQ:

1) Если одна из двух частей имеет размеры PxQ или QxP, то в этом случае остатков не будет и на место ставим 0.
2) В противном случае на место ставим P*Q. Т.е. если в эту часть не влезет ни одна из исходных фигур.
Затем перебираем все возможные разрезы по горизонтали и вертикали до P/2 и Q/2 соответственно (дальше делить нет смысла, потому что значения будут повторяться) и считаем сумму элементов [A;Q] и [P-A;Q] и также [P;B] и [P;Q-B] (это и есть разрезы по координатам A и B) и среди этих сумм находим минимальную сумму остатков.

Более того, очевидно, что при повороте исходного прямоугольника на 90 градусов результат не изменится, поэтому алгоритм можно ещё ускорить примерно вдвое, считая только элементы за главной диагональю.

ЗЫ Не забываем нажимать на весы.