Разрезать прямоугольник

[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
Поворачивать детали можно. А разрезать только от края до края. Зигзагами нельзя.
Подскажите, как написать максимально быстрый алгоритм?
Вроде как, нужно реализовать алгоритм "Метод ветвей и границ", но как его связать с задачей?

[Pavia]

Перечитал задачу. Задача не совсем корректная. Нет минимального значения есть единственное.
Ответ $s=X*Y- X1*Y1 -X2*Y2=10*10-2*9-3*4=100-18-12=70$
Еще в задаче не сказано о том вообще можно вырезать из одного прямоугольника 2 других.
Проверить это не трудно. Берем и проверяем все случаи их немного.

if (x1+x2<x) or
   (((x1+y2)<x) and (x2<y)) or
   (((y1+x2)<x) and (x1<y)) or
   (((y1+y2)<x) and (x2<y) and (x1<y)) or

   (y1+y2<y) or
   (((y1+x2)<y) and (y2<x)) or
   (((x1+y2)<y) and (y1<x)) or
   (((x1+x2)<y) and (y2<x) and (y1<x))
   then разрезать можно.

Все других вариантов размещения нет.

[venco]

Насколько я понял, можно вырезать разное количество деталей обоих размеров, главное, чтобы остаток был минимальный.
Например: 100 - 6*(3*4) - 1*(9*2) = 10.

Sheril в сообщении #300113 писал(а):

Вроде как, нужно реализовать алгоритм "Метод ветвей и границ", но как его связать с задачей?

Используйте динамическое программирование.

[venco]

venco в сообщении #300381 писал(а):

Насколько я понял, можно вырезать разное количество деталей обоих размеров, главное, чтобы остаток был минимальный.
Например: 100 - 6*(3*4) - 1*(9*2) = 10.

Может оказаться, что количество деталей двух размеров должно быть одинаковым. В условии об этом не сказано, но может подразумеваться.
К сожалению, при таких условиях в приведённом примере опять можно получить остаток 10:
100-3*(3*4)-3*(9*2) = 10, (3*4 сложены в прямоугольник 9*4, а 9*2 - в 9*6).
Если требовать одинаковое количество, то решение сложнее и медленнее.