Backtracking to get 2 sums as similar as possible

0

It happens that I have to deliver a code which I must solve with backtracking, but I have gone hand in hand the way of adding and differentiating the sums to compare them. The problem is that; Given a list of numbers, of size X, you have to make 2 lists, each list must be of size X / 2 and at the same time each one must add the closest possible quantity to each other. axis;

lista={1,3,5,7};

n=4; //(length de lista).

the result will be:

lista1={1,7};  y lista2={3,5};

the sum of the numbers in list1 = 8, as well as list2. That sum of the 2 resulting lists should be as similar as possible. advance but it is not very good to unite all the ideas.

public static int[] lista;
public static int n;

public static int suma1;
public static int suma2;////


public static boolean esPosible(int pos1, int pos2) {
    if (pos1 >= 0 && pos2 >= 0 && pos1 < n && pos2 < n) {
        return true;
    }
    return false;
}

public static void prueba(int suma1, int suma2, int pos1, int pos2) {
    StdOut.println(n);
    int mitad1 = 0, mitad2 = 0;
    if (n % 2 == 0) {
        mitad2 = mitad1 = n / 2;
    } else {
        mitad1 = (n + 1) / 2;
        mitad2 = (n - 1) / 2;
    }

    if ((suma1 - suma2) == 0) {
        StdOut.println("el valor de las sumas para el caso sera; suma 1= " + suma1 + " y suma 2= " + suma2);
        return;
    } else {
        if (esPosible(pos1, pos2)) {

            if (pos1 == n) {
                pos1 = 0;
                prueba(suma1, suma2, pos1 + 1, pos2 + 1);
            }


            suma1 = lista[pos1] + lista[pos2];

            prueba(suma1, suma2, pos1 + 1, pos2);

        }
    }

help!

    
asked by user99470 10.09.2018 в 01:04
source

1 answer

0

I do not know, but I can think of this:

  • add all the number of the initial array, according to your example it would be 16.
  • we divide that result in 2, that means that each array must add 8.
  • then we look for the ideal number to achieve the ideal sum (8). if the array is ordered we can start with the largest number and add up to get an 8.
  • I do not know if my pseudo code serves.

        
    answered by 10.09.2018 в 01:52