algorithm - 从给定长度的线段构造最大可能的矩形

Question

我最近参加了一个比赛，有人问我这个问题。给定一个长度数组，使用所有长度可以组成的最大矩形的面积是多少。长度可以增加但不能在两者之间中断。

例子:[ 4,2,4,4,6,8 ] 给定这个数组，我们能做的最好的事情就是像这样制作一个边长为 8 和 6 的矩形。

面积为 8 * 6 = 48。

我是一个初学者，即使经过长时间的努力思考如何去做，我也无能为力。我不是在寻找解决方案，但如果有任何线索可以帮助我朝着正确的方向前进，我们将不胜感激。

TIA

编辑:有人指出(评论现已删除)仅凭提示而不发布一些代码很难解释解决方案。如有必要，请发布代码。

Answer 1

问题是NP-Hard ，因此 backtracking解决方案[或@vhallac 建议的其他指数解决方案] 将是您的最佳选择，因为对于此类问题，未知[并且如果 P!=NP，则不存在] 多项式解决方案。

NP-硬度证明:
首先，我们知道一个矩形由4条边组成，它们成对相等[e1=e2,e3=e4]。
我们将证明如果存在多项式算法A对于这个问题，我们也可以解决Partition Problem , 通过以下算法:

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 < sum*5，因此有 2 条边的长度为 sum*5，因为其他 2 条边必须使用所有剩余长度[作为指定的问题]，每个其他边缘实际上是长度 (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)

编辑 2:
正如评论中所讨论的，这个答案表明不仅很难找到 BEST 矩形，而且也很难找到 ANY 矩形，从而导致这个问题很难heuristic解决方案。