algorithm - resta - Subconjuntos de suma igualitaria híbridos

problema de la suma de subconjuntos

Question

El problema es el siguiente:

Se te da un conjunto de enteros positivos {a1, a2, a3, ..., an} en los que no hay los mismos números (a1 existe solo una vez, a2 existe solo una vez, ...) ej. A = {12, 5 , 7, 91}. Pregunta: ¿Hay dos subconjuntos disjuntos de A, A1 = {b1, b2, ..., bm} y A2 = {c1, c2, ..., ck} de modo que b1 + b2 + ... + bm = c1 + c2 + ... + ck?

Tenga en cuenta lo siguiente: no es obligatorio que A1 y A2 cubran A, por lo que el problema no se reduce automáticamente al problema de la suma de subconjuntos. ej. A = {2,5,3,4,8,12} A1 = {2,5} entonces la suma de A1 es 7 A2 = {3,4} entonces la suma de A2 es 7. Encontramos dos subconjuntos disjuntos de A con la propiedad descrita por lo que el problema está resuelto.

¿Como puedó resolver esté problema? ¿Puedo hacer algo mejor que encontrar todos los subconjuntos posibles (disjuntos), calcular sus sumas y encontrar dos sumas iguales?

Gracias por tu tiempo.

Answer 1

Creo que puedes resolverlo igual que el problema de suma de subconjuntos. Tome la función booleana Q (i, s) que es verdadera si a0, a1, ..., ai tiene un subconjunto que suma a s y contiene ai. Puede calcularlo para todos los i y s usando la programación dinámica (este es el enfoque estándar). Luego, puede escanear todos los valores de Q para s que tengan más de un valor verdadero en su fila asociada.

Si tal s existe, significa que encontraste dos subconjuntos diferentes que tienen la misma suma. Puede que no sean disjuntos, pero luego puede eliminar los elementos comunes de cada conjunto y obtener dos conjuntos disjuntos con sumas iguales. Uno de ellos podría estar vacío, sin embargo.

Answer 2

Si la respuesta es no, entonces la suma de todos los n números es al menos 2 ^ n-1. Entonces, si n es grande y los números son enteros de 32 bits, por ejemplo, la respuesta es casi siempre sí. Si n es pequeño, probablemente puedas usar la fuerza bruta.

El caso más difícil es probablemente cuando n es alrededor de 30.

Answer 3

No hay problema, aquí hay una solución O(1) .

A1 = {}; 
A2 = {};
sum(A1) == sum(A2) /* == 0 */

QED.

En serio, una optimización que puede realizar (suponiendo que estamos hablando de números positivos) es verificar únicamente subconjuntos menores o iguales a la sum(A)/2 .

Para cada elemento en A hay tres opciones que lo hacen O(3^N) :

1. Ponlo en A1
2. Ponlo en A2
3. Descártalo

Aquí hay una solución ingenua en Perl (que cuenta las coincidencias, puedes tener un retorno anticipado si solo quieres probar la existencia).

use List::Util qw/sum/;

my $max = sum(@ARGV)/2;
my $first = shift(@ARGV); # make sure we don''t find the empty set (all joking aside) and that we don''t cover same solution twice (since elements are unique)
my $found = find($first,0, @ARGV);
print "Number of matches: $found/n";

sub find {
    my ($a, $b, @tail) = @_;
    my $ret = $a == $b? 1 : 0; # are a and b equal sub-sets?
    return $ret unless @tail;

    my $x = shift @tail;
    $ret += find($a + $x, $b, @tail) if $a + $x <= $max; # put x in a
    $ret += find($a, $b + $x, @tail) if $b + $x <= $max; # put x in b
    return $ret + find($a, $b, @tail); # discard x
}

Answer 4

Este problema parece ser al menos tan difícil como SUBSET-SUM. Si podemos encontrar dos subconjuntos de A: B = {b1, ..., bp} y C = {c1, ..., cq} tales que b1 + ... + bp = -c1 -...- cq, o si determinamos que ninguno existe, entonces hemos resuelto SUBSET-SUMA (A) (ignorando el caso trivial donde 0 ∈ A).

No estoy seguro de lo que quiere decir con que no es obligatorio que B y C cubran A, por lo que el problema no se reduce automáticamente al problema de la suma de subconjuntos. Por favor, consulte la definición de SUBSET-SUM.