我最近参加了一个比赛，被问及一个问题：给定一个长度数组，用所有长度组成的矩形的面积最大是多少。长度可以相加，但不能在中间断开。
例如：
[ 4,2,4,4,6,8 ] 给定此数组，我们能够得到一个边长为8和6的矩形，如下所示。
从而得到面积为8 * 6 = 48。
作为初学者，即使经过长时间思考，我也无法想出如何解决这个问题。我不是在寻找解决方案，而是希望有任何提示可以引导我正确的方向。
TIA
编辑：有人指出（评论已删除），仅使用提示很难解释解决方案，如果必要，请贴出代码。
使用给定长度的线段构造最大可能的矩形
21
- johne
15
1请使用codegolf.stackexchange.com。 - Hans Passant
13我认为这是一个很好的问题，询问可能的算法来解决这个问题。投票支持重新开放。 - Howard
我也被 codegolf 投票出局了！显然我的问题在那里也不合适。有人能建议去哪里寻求帮助吗？如果这个地方不合适的话，我很抱歉，但是类似 codegolf 的另一个建议会很有帮助。 - johne
3在最坏情况下，我们需要处理多少个长度？这些木棍可以有多大？对大O复杂度有一个界限有助于问题解决（同时在比赛的问题陈述中应包含此类信息）。 - hugomg
这个问题是NP-完全问题，但不是在强意义下的。这意味着如果输入大小（如用于创建矩形边的数字2、4、8、6、5）不大，那么这可以在多项式时间内完成。实际上，解决方案为“S*n”，其中S是线段长度之和，“n”是可用输入数量。实际上，您可以使用动态规划进行此操作。请参阅WIKI伪多项式时间算法以了解分区。 - Saeed Amiri
显示剩余10条评论
3个回答
11
这个问题是NP难的，因此通过回溯解决方案[或者像@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) 如果存在分割为S1，S2的分区，则存在一矩形边长为：(sum*5),(sum*5),S1,S2，算法将返回True。
(2) 如果算法返回True，则长度上有一个可用的矩形，因为 a1 + a2 + ... + an < sum*5，所以存在两个长度为 sum*5 的边，由于另外两条边必须使用所有剩余的长度 [如问题所述]，每个其他边实际上的长度为(a1 + a2 + ... + an)/2，因此问题存在合法的划分。
结论： 存在一个约化 PARTITION <=（p）this problem，因此，该问题是NP难的。
编辑：
回溯解决方案很简单，获取所有可能的矩形，并检查它们中哪一个是最佳的。
回溯解决方案：伪代码：
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：
正如评论中所讨论的那样，这个答案不仅展示了找到最佳矩形的难度，同时也很难找到任何矩形，这使得使用启发式方法解决这个问题变得困难。
- amit
8
@AndreyT：你当然是对的，这是4部分划分问题的优化问题。我的答案不仅表明找到最佳矩形很困难，而且找到是否存在任何矩形也很困难。 - amit
1你说得对。实际上，这是一个涉及4个分区的“嵌套”Partition问题，需要在每一对分区内获得完美的平等，并且还需要最小化这些对之间的差异。每个要求本身都是一个Partition问题：一个是“二进制”形式，另一个是“优化”形式。 - AnT stands with Russia
很棒的答案！现在我想补充一些东西：a）如果只有几根木棍，检查所有组合是可以的。如果有许多小木棍，可能可以使用动态规划解决方案？b）鉴于这是一个编程竞赛，一个被接受的解决方案可能需要更加精细，也许通过利用对称性和使用修剪策略来实现。 - hugomg
@missingno: (a) 可能存在一种动态规划的解决方案，比暴力搜索更好，但仍然是指数级别的！（即 TSP：暴力搜索 O(n!)，动态规划 O((n^2)*(2^n))），因此除非 P=NP，否则这个问题根本没有多项式解决方案 [当然包括动态规划]。(b) OP 说输入大约有10个数字，4^10=2^20~=1m，所以回溯法应该可以解决。 - amit
@amit：我知道。只是有一种普遍的权衡：小N，大尺寸->测试所有组合更快；大N，小尺寸->在尺寸上进行动态规划更快。 - hugomg
显示剩余3条评论
2
这里有一个Python解决问题的方案。它并没有进行优化。例如，我甚至在检查4,2之后还会检查2,4。但是为了展示如何找到解决方案，我认为这已经足够好了。
def all_but(lst, pos):
return lst[0:pos]+lst[pos+1:]
def find_sets_with_len(segs, l):
for i in range(0, len(segs)):
val = segs[i]
if (val == l):
yield [val], all_but(segs, i)
if (val < l):
for soln, rest in find_sets_with_len(all_but(segs, i), l - val):
yield [val]+soln, rest
def find_rect(segs, l1, l2):
for side1, rest1 in find_sets_with_len(segs, l1):
for side2, rest2 in find_sets_with_len(rest1, l1):
for side3, rest3 in find_sets_with_len(rest2, l2):
return [side1, side2, side3, rest3]
def make_rect(segs):
tot_len = sum(segs)
if (tot_len %2) == 0:
opt_len=tot_len/4
for l in range(opt_len, 0, -1):
sides = find_rect(segs, l, tot_len/2-l)
if sides is not None:
print(sides)
return sides
print("Can't find any solution")
make_rect([4,2,4,4,6,8])
这个想法很简单：首先计算最佳长度（即使正方形），然后从最佳长度开始搜索所有内容，并向下搜索到一个边长为1的正方形。对于每个长度，枚举计算长度一侧的所有集合，然后枚举相同长度的另一侧的所有集合，如果我可以找到剩余长度的另一个集合（即
total_len/2 减去我正在查看的边长），那么我就得到了最佳解决方案。这发生在find_rect()函数中。- vhallac
0
嗯，我有点无聊，所以玩了一下Java来积累一些经验，可能会写得不好且没有调优，因为我试图提高我的编程技能，欢迎评论。我的电脑可以处理小数组的请求：）
输出结果如下：
Largest rectangle range is ; 48
-------------------------------------------------
input values; [ 4,2,4,4,6,8,9 ]
-------------------------------------------------
Array details of the rectangle:
A1: [ 6 ]
B1: [ 8 ]
A2: [ 2,4 ]
B2: [ 4,4 ]
使用Kenneth算法的combination.class;
导入java.math.BigInteger;
public class Combination {
/**
* Burak
*/
private int[] a;
private int n;
private int r;
private BigInteger numLeft;
private BigInteger total;
public Combination (int n, int r) {
if (r > n) {
throw new IllegalArgumentException ();
}
if (n < 1) {
throw new IllegalArgumentException ();
}
this.n = n;
this.r = r;
a = new int[r];
BigInteger nFact = getFactorial (n);
BigInteger rFact = getFactorial (r);
BigInteger nminusrFact = getFactorial (n - r);
total = nFact.divide (rFact.multiply (nminusrFact));
reset ();
}
//------
// Reset
//------
public void reset () {
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
numLeft = new BigInteger (total.toString ());
}
//------------------------------------------------
// Return number of combinations not yet generated
//------------------------------------------------
public BigInteger getNumLeft () {
return numLeft;
}
//-----------------------------
// Are there more combinations?
//-----------------------------
public boolean hasMore () {
return numLeft.compareTo (BigInteger.ZERO) == 1;
}
//------------------------------------
// Return total number of combinations
//------------------------------------
public BigInteger getTotal () {
return total;
}
//------------------
// Compute factorial
//------------------
private static BigInteger getFactorial (int n) {
BigInteger fact = BigInteger.ONE;
for (int i = n; i > 1; i--) {
fact = fact.multiply (new BigInteger (Integer.toString (i)));
}
return fact;
}
//--------------------------------------------------------
// Generate next combination (algorithm from Rosen p. 286)
//--------------------------------------------------------
public int[] getNext () {
if (numLeft.equals (total)) {
numLeft = numLeft.subtract (BigInteger.ONE);
return a;
}
int i = r - 1;
while (a[i] == n - r + i) {
i--;
}
a[i] = a[i] + 1;
for (int j = i + 1; j < r; j++) {
a[j] = a[i] + j - i;
}
numLeft = numLeft.subtract (BigInteger.ONE);
return a;
}
}
以及主要Combinator.class;
import java.util.*;
公共类别组合器 {
/**
* @param args
*/
private static int[] ad;
private static int[] bd;
private static String a1;
private static String a2;
private static String b1;
private static String b2;
private static int bestTotal =0;
public static void main(String[] args) {
int[] array={4,2,4,4,6,8,9};
getBestCombination(array, 1);
if(bestTotal <= 0){
System.out.println("System couldnt create any rectangle.");
}else{
System.out.println("Largest rectangle range is ; " + bestTotal);
System.out.println("-------------------------------------------------");
System.out.println("input values; " + parseArrayToString(array));
System.out.println("-------------------------------------------------");
System.out.println("Array details of the rectangle:");
System.out.println("A1: " + a1);
System.out.println("B1: " + b1);
System.out.println("A2: " + a2);
System.out.println("B2: " + b2);
}
}
private static void getBestCombination(int[] array, int level){
int[] a;
int[] b;
int bestPerimeter = getTotal(array,true);
Vector<Vector<Integer>> results = null;
for(int o=array.length-1;o>=1;o--){
for(int u=bestPerimeter;u>=1;u--){
results = Combinator.compute (array, o, u);
if(results.size() > 0){
for(int i=0;i<results.size();i++){
a = new int[results.elementAt(i).size()];
for(int j = 0;j<results.elementAt(i).size();j++){
a[j] = results.elementAt(i).elementAt(j);
}
b = removeItems(array, results.elementAt(i));
if(level == 1){
getBestCombination(a,2);
getBestCombination(b,3);
}else if(level == 2){
ad = a;
bd = b;
}else{
getBestCombination(a,4);
getBestCombination(b,4);
if(getTotal(ad, false) == getTotal(a, false) && getTotal(bd, false) == getTotal(b, false)){
if(bestTotal<(getTotal(ad, false)*getTotal(bd, false))){
bestTotal = getTotal(ad, false)*getTotal(bd, false);
a1 = parseArrayToString(ad);
a2 = parseArrayToString(a);
b1 = parseArrayToString(bd);
b2 = parseArrayToString(b);
}
}else if(getTotal(ad, false) == getTotal(b, false) && getTotal(bd, false) == getTotal(a, false)){
if(bestTotal<(getTotal(ad, false)*getTotal(bd, false))){
bestTotal = getTotal(ad, false)*getTotal(bd, false);
a1 = parseArrayToString(ad);
a2 = parseArrayToString(b);
b1 = parseArrayToString(bd);
b2 = parseArrayToString(a);
}
}
}
}
}
}
}
}
private static String parseArrayToString(int[] items){
String s = "[ ";
for(int i=0;i<items.length;i++){
if(i!=items.length-1){
s = s + items[i] + ",";
}else{
s = s + items[i];
}
}
s = s + " ]";
return s;
}
@SuppressWarnings("rawtypes")
private static int[] removeItems(int[] array, Vector items){
ArrayList<Integer> res = new ArrayList<Integer>();
for(int i=0;i<array.length;i++){
res.add(array[i]);
}
for(int u = 0;u<items.size();u++){
res.remove(items.elementAt(u));
}
int[] results = new int[res.size()];
for(int o=0;o<res.size();o++){
results[o] = res.get(o);
}
return results;
}
private static int getTotal(int[] array,boolean bestPerimeter){
int sum = 0;
for (int i = 0; i < array.length; i++) {
sum += array[i];
}
if(bestPerimeter == true){
if(sum%2!=0){
sum = sum -1;
}
sum = sum/2;
}
//System.out.println(sum);
return sum;
}
@SuppressWarnings("rawtypes")
private static int getSum (Vector v) {
int sum = 0;
Integer n;
for (int i = 0; i < v.size (); i++) {
n = (Integer) v.elementAt(i);
sum += n.intValue ();
}
return sum;
}
@SuppressWarnings({ "rawtypes", "unchecked" })
public static Vector<Vector<Integer>> compute (int[] array, int atATime, int desiredTotal) {
int[] indices;
Combination gen = new Combination (array.length, atATime);
Vector results = new Vector ();
Vector combination;
int sum;
Integer intObj;
while (gen.hasMore ()) {
combination = new Vector ();
indices = gen.getNext ();
for (int i = 0; i < indices.length; i++) {
intObj = new Integer (array[indices[i]]);
combination.addElement (intObj);
}
sum = getSum (combination);
if (sum == desiredTotal) {
Collections.sort (combination);
if (!results.contains (combination)) {
results.addElement (combination);
}
}
}
return results;
}
}
- HRgiger
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接