Dada una matriz, debe encontrar el máximo posible de dos sumas iguales, puede excluir elementos.

Es decir, 1,2,3,4,6 recibe una matriz podemos tener un máximo de dos sumas iguales como 6 + 2 = 4 + 3 + 1

Es decir, 4,10,18, 22, podemos obtener dos sumas iguales como 18 + 4 = 22

¿Cuál sería su enfoque para resolver este problema además de la fuerza bruta para encontrar todos los cálculos y verificar dos posibles sumas iguales?

Edición 1: el número máximo de elementos de la matriz es N <= 50 y cada elemento puede tener hasta 1 <= K <= 1000

Editar 2: Aquí está mi solución https://ideone.com/cAbe4g, lleva demasiado tiempo donde el tiempo dado el límite es de 5 segundos para cada caso.

Edición 3: - La suma total de elementos no puede ser mayor que 1000.

15
Atiq 9 sep. 2018 a las 15:47

3 respuestas

La mejor respuesta

Enfoque recomendado

Sugiero resolver esto usando DP donde en lugar de rastrear A, B (el tamaño de los dos conjuntos), en lugar de seguir A + B, A-B (la suma y la diferencia de los dos conjuntos).

Luego, para cada elemento de la matriz, intente agregarlo a A, B o ninguno.

La ventaja de realizar un seguimiento de la suma / diferencia es que solo necesita realizar un seguimiento de un valor único para cada diferencia, es decir, el valor más grande de la suma que ha visto para esta diferencia.

Para mayor eficiencia, le recomiendo que recorra los elementos en orden de menor a mayor y deje de actualizar el DP una vez que se alcance la mayor diferencia observada hasta el momento.

También solo puede almacenar el valor absoluto de la diferencia e ignorar cualquier diferencia mayor que 25000 (ya que será imposible que la diferencia regrese a 0 desde este punto).

Código de ejemplo de Python

from collections import defaultdict

def max_equal_sum(E):
    D=defaultdict(int)            # Map from abs difference to largest sum
    D[0]=0                        # Start with a sum and difference of 0
    for a in E:                   # Iterate over each element in the array
        D2=D.copy()               # Can keep current sum and diff if element is skipped
        for d,s in D.items():     # d is difference, s is sum
            s2 = s+a              # s2 is new sum
            for d2 in [d-a,d+a]:  # d2 is new difference
                D2[abs(d2)] = max(D2[abs(d2)],s2) # Update with largest sum
        D=D2
    return D[0]/2                 # Answer is half the sum of A+B for a difference of 0

print max_equal_sum([1,2,3,4,6])  # Prints 8
print max_equal_sum([4,10,18,22]) # Prints 22
15
Peter de Rivaz 9 sep. 2018 a las 18:58

Para cada elemento en la matriz, hay tres posibilidades. (i) Incluir el elemento en el primer conjunto (ii) Incluir el elemento en el segundo conjunto (iii) No incluye el elemento en ningún conjunto siempre que la suma del primer y segundo conjunto sea igual a actualizar la respuesta.

   public class Main
{
    static int ans = -1;
   public static void find(int[] arr,int sum1,int sum2,int start)
   {    if(sum1==sum2)
         ans = Math.max(ans,sum1);
        if(start==arr.length)
          return;
        find(arr,sum1+arr[start],sum2,start+1);
        find(arr,sum1,sum2+arr[start],start+1);
        find(arr,sum1,sum2,start+1);

   }
   public static void main(String[] args)
   {
       int[] arr = new int[]{1,2,100,101,6,100};
       ans = -1;
       find(arr,0,0,0);
       System.out.println(ans);
   }
}
0
M.R.Srinivasan 29 mar. 2020 a las 10:55

El conjunto más grande con valores de 0 a 1000 que no tiene dos subconjuntos con igual suma tiene 9 elementos, por ejemplo:

{1, 2, 4, 8, 16, 32, 64, 128, 256, 512}

Si agrega un décimo elemento, será igual a la suma de un subconjunto de los nueve valores anteriores.

Si encuentra dos subconjuntos con igual suma después de haber excluido más de 9 elementos, entonces se pueden sumar dos sumas iguales de los elementos excluidos para formar sumas iguales mayores; Esto significa que nunca debe excluir más de 9 elementos.

La suma de los elementos excluidos en el rango de 0 a 1000. Construir un tamiz para verificar qué valores en este rango se pueden formar con los elementos en el conjunto tomará como máximo 50 × 1000 pasos. (Podemos almacenar el número mínimo de valores que se suman a cada suma en lugar de un valor booleano, y usar eso para incluir solo sumas que se pueden hacer con 9 elementos o menos).

Si luego miramos las sumas de los números excluidos de pequeño a grande, eso significa mirar las sumas de los números incluidos de mayor a menor. Para cada suma de valores excluidos, verificamos qué elementos (hasta 9) pueden formar esta suma (obviamente no es un paso trivial, pero sabemos que el número de elementos está entre el valor mínimo almacenado en el tamiz y 9), y esto nos da el conjunto de excluidos y por lo tanto también el conjunto de números incluidos. Luego usamos una técnica de tamizado similar para verificar si los números incluidos pueden formar la media suma; esto estará en el rango de 1 a 500 y tomará como máximo 50 × 500 pasos.

En todo esto, por supuesto, hay que considerar la impar / par: si la suma total es impar, un subconjunto con una suma impar debe ser excluido; si la suma total es par, solo se deben excluir los subconjuntos con una suma par.

Realmente no he descubierto cómo generar la entrada del peor de los casos para esto, por lo que es difícil juzgar la complejidad del peor de los casos; pero creo que el caso promedio debería ser factible.


Estas son algunas de las partes en acción. Primero, el tamiz para encontrar las sumas de los conjuntos de hasta 9 valores que pueden excluirse (y tener la impar / par correcta) probadas con 20 valores con una suma de 999:

function excludedSums(values) {
    var sieve = [0];
    for (var i in values) {
        var temp = [];
        for (var j in sieve) {
            if (sieve[j] == 9) continue;
            var val = values[i] + Number(j);
            if (!sieve[val] || sieve[j] + 1 < sieve[val]) {
                temp[val] = sieve[j] + 1;
            }
        }
        for (var j in temp) {
            sieve[j] = temp[j];
        }
    }
    var odd = values.reduce(function(ac, el) {return ac + el}, 0) % 2;
    for (var i in sieve) {
        if (Number(i) % 2 != odd) delete sieve[i];
    }
    return sieve;
}
var set = [40,7,112,15,96,25,49,49,31,87,39,8,79,40,73,49,63,55,12,70];
var result = excludedSums(set);
for (var i in result) document.write(i + ", ");

A continuación, los conjuntos de hasta 9 valores con una cierta suma. En el ejemplo anterior, vemos que p. se pueden excluir uno o más conjuntos con la suma 99; Veamos cuáles son estos conjuntos:

function excludedSets(values, target) {
    var sieve = [[[]]];
    for (var i in values) {
        var temp = [];
        for (var j in sieve) {
            var val = values[i] + Number(j);
            if (val > target) continue;
            for (var k in sieve[j]) {
                if (sieve[j][k].length < 9) {
                    if (!temp[val]) temp[val] = [];
                    temp[val].push(sieve[j][k].concat([values[i]]));
                }
            }
        }
        for (var j in temp) {
            if (!sieve[j]) sieve[j] = [];
            for (var k in temp[j]) {
                sieve[j].push(temp[j][k].slice());
            }
        }
    }
    return sieve[target];
}

var set = [40,7,112,15,96,25,49,49,31,87,39,8,79,40,73,49,63,55,12,70];
var result = excludedSets(set, 99);
for (var i in result) document.write(result[i] + "<br>");

(Verá algunos duplicados en la salida, porque, por ejemplo, el valor 49 aparece tres veces en el conjunto).

Ahora probemos si el conjunto sin valores excluidos se puede dividir en dos. Vemos que la suma 99 se puede formar, p. por los valores 87 y 12, por lo que los excluimos del conjunto y obtenemos un conjunto de 18 valores con la suma 900. Ahora verificamos si la media suma 450 puede formarse agregando valores del conjunto:

function sumPossible(values, target) {
    var sieve = [true];
    for (var i in values) {
        var temp = [];
        for (var j in sieve) {
            var val = values[i] + Number(j);
            if (val < target) temp[val] = true;
            else if (val == target) return true;
        }
        for (var j in temp) sieve[j] = temp[j];
    }
    return false;
}
var set = [40,7,112,15,96,25,49,49,31,39,8,79,40,73,49,63,55,70];
document.write(sumPossible(set, 450));

Entonces 450 es una de las posibles medias sumas para este conjunto. Obviamente no es la más grande, porque elegimos al azar la suma 99 para excluirla como ejemplo, en lugar de iterar sobre todas las sumas de pequeñas a grandes; de hecho, la primera opción, excluyendo el valor 7, habría llevado a la media suma máxima de 496.

Cabe señalar que cuanto más grande es el conjunto, más probable es que el conjunto se pueda dividir por la mitad (si tiene una suma par, o con el valor impar más pequeño eliminado si tiene una suma impar). Una prueba con millones de conjuntos de valores aleatorios con una suma par de hasta 1000 reveló que no hay un solo conjunto que no se pueda dividir por la mitad, para cualquier tamaño de conjunto superior a 28. (Por supuesto, es posible crear dicho conjunto, por ejemplo 49 unos y un solo 51.)

2
m69 ''snarky and unwelcoming'' 12 sep. 2018 a las 04:28