Проблема в NP-Hard , поэтому лучшим решением будет ваш возвратный вариант [или другое экспоненциальное решение, предложенное @vhallac], поскольку неизвестно [иесли P! = NP, полиномиального решения для такого рода задач не существует.
NP-твердость:
Во-первых, мы знаем, что прямоугольник состоит из 4 ребер, которые равны в парах [e1 = e2, e3 = e4].
Мы покажем, что если для этой задачи существует полиномиальный алгоритм A, мы также можем решить проблему разбиения следующим алгоритмом:
input: a group of numbers S=a1,a2,...,an
output: true if and only if the numbers can be partitioned
algorithm:
sum <- a1 + a2 + .. + an
lengths <- a1, a2 , ... , an , (sum*5), (sum*5)
activate A with lengths.
if A answered there is any rectangle [solution is not 0], answer True
else answer False
Корректность:
(1) если есть разделение на S, пусть это будет S1, S2, есть также прямоугольник с ребрами: (sum*5),(sum*5),S1,S2, и алгоритм выдаст True.
(2) если алгоритм выдает True, имеется прямоугольник, доступный по длине, так как a1 + a2 + ... + an (a1 + a2 + ... + an)/2, и, таким образом, существует законное разделение проблемы.
Заключение: Тамявляется сокращением PARTITION<=(p) this problem, и, таким образом, эта проблема является NP-Hard
РЕДАКТИРОВАТЬ:
решение по возврату довольно просто, получить все возможные прямоугольникии проверьте каждый из них, чтобы увидеть, какой из них лучший.
решение для возврата: псевдокод:
getAllRectangles(S,e1,e2,e3,e4,sol):
if S == {}:
if legalRectangle(e1,e2,e3,e4):
sol.add((e1,e2,e3,e4))
else: //S is not empty
elem <- S[0]
getAllRectangles(S-elem,e1+elem,e2,e3,e4,sol)
getAllRectangles(S-elem,e1,e2+elem,e3,e4,sol)
getAllRectangles(S-elem,e1,e2,e3+elem,e4,sol)
getAllRectangles(S-elem,e1,e2,e3,e4+elem,sol)
getRectangle(S):
RECS <- new Set
getAllRectangles(S,{},{},{},{},RECS)
getBest(RECS)
EDIT2:
Как обсуждалось в комментариях, этот ответ показывает не только то, что трудно найти ЛУЧШИЙ прямоугольник, также трудно найти ЛЮБОЙ прямоугольник, что затрудняет эту проблему и для эвристических решений.