Построить максимально возможный прямоугольник из сегментов линии заданных длин

Ответ 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 ребра с суммой длины * 5, так как 2 других ребра должны быть сделаны с использованием всех оставшихся длин [в качестве заданного вопроса], каждый другой край фактически имеет длину (a1 + a2 + ... + an)/2, и, следовательно, существует законная раздел к проблеме.

Вывод: Существует сокращение PARTITION<=(p) this problem, и, таким образом, эта проблема NP-Hard

EDIT: Решение backtracking - довольно просто, получить все возможные прямоугольники и проверить каждый из них, чтобы узнать, какой из них лучше. Решение для обратного отслеживания: псевдокод:

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:
Как обсуждалось в комментариях, этот ответ показывает, что трудно найти ЛУЧШИЙ прямоугольник, также трудно найти ЛЮБОЙ прямоугольник, что затрудняет эту проблему для heuristic.

Ответ 2

Вот одно решение проблемы в Python. Он не оптимизирован вообще. Я даже проверю 2, 4 после проверки 4,2, например. Но для того, чтобы показать, как вы можете найти решение, я думаю, что это достаточно хорошо.

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 с одной стороны. Для каждой длины перечислите все множества для одной стороны claculated length, затем перечислите все множества для противоположной стороны (той же длины), тогда, если я могу найти еще один набор оставшейся длины (т.е. total_len/2 минус длина стороны, на которую я смотрю), тогда у меня есть лучшее решение. Это происходит в функции find_rect().

Ответ 3

Ну, мне становится немного скучно, поэтому играйте с 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 ]

comb.class с использованием алгоритма Кеннета;

import 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. *;

Комбинатор public class {

/**
 * @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;
      }

}