构造给定长度的线段之外的最大可能矩形

Question

我最近参加了一个竞赛,我被问到这个问题.给定一个长度为数组的数组,使用所有长度可以制作最大矩形的面积.可以添加长度,但不能间断.

示例: [ 4,2,4,4,6,8 ]给定此数组,我们所能做的最好是制作一个像8和6这样的矩形.

给出8*6 = 48的面积.

我是一个初学者,即使经过长时间的努力思考如何做到这一点,我也无法到达任何地方.我不是在寻找解决方案,但任何能够在正确的方向上推动我的线索都将受到赞赏.

TIA

编辑:有人指出(评论已删除),很难用解释来解释解决方案,而不是发布一些代码.如有必要,请发布代码.

Answer 1

问题是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 + ... + a <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:
正如评论中所讨论的,这个答案显示,不仅难以找到最佳矩形,也很难找到任何矩形,这也使得启发式解决方案难以解决这个问题.