Algoritmo para dividir una lista de números en 2 listas de suma igual

Dynamic programming es la solución que estás buscando.

Ejemplo con [4, 3, 10, 3, 2, 5]:

X-Axis: Reachable sum of group.        max = sum(all numbers) / 2    (rounded up)
Y-Axis: Count elements in group.       max = count numbers / 2       (rounded up)

      1  2  3  4  5  6  7  8  9 10 11 12 13 14
 1  |  |  |  | 4|  |  |  |  |  |  |  |  |  |  |       //  4
 2  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
 3  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

      1  2  3  4  5  6  7  8  9 10 11 12 13 14
 1  |  |  | 3| 4|  |  |  |  |  |  |  |  |  |  |       //  3
 2  |  |  |  |  |  |  | 3|  |  |  |  |  |  |  |
 3  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

      1  2  3  4  5  6  7  8  9 10 11 12 13 14
 1  |  |  | 3| 4|  |  |  |  |  |10|  |  |  |  |       // 10
 2  |  |  |  |  |  |  | 3|  |  |  |  |  |10|10|
 3  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

      1  2  3  4  5  6  7  8  9 10 11 12 13 14
 1  |  |  | 3| 4|  |  |  |  |  |10|  |  |  |  |       //  3
 2  |  |  |  |  |  | 3| 3|  |  |  |  |  |10|10|
 3  |  |  |  |  |  |  |  |  |  | 3|  |  |  |  |

      1  2  3  4  5  6  7  8  9 10 11 12 13 14
 1  |  | 2| 3| 4|  |  |  |  |  |10|  |  |  |  |       //  2
 2  |  |  |  |  | 2| 3| 3|  |  |  |  | 2|10|10|
 3  |  |  |  |  |  |  |  | 2| 2| 3|  |  |  |  |

      1  2  3  4  5  6  7  8  9 10 11 12 13 14
 1  |  | 2| 3| 4| 5|  |  |  |  |10|  |  |  |  |       //  5
 2  |  |  |  |  | 2| 3| 3| 5| 5|  |  | 2|10|10|
 3  |  |  |  |  |  |  |  | 2| 2| 3| 5| 5|  |  |
                                       ^

12 es nuestro número de la suerte! Retrocediendo para obtener el grupo:

12 - 5 = 7        {5}
 7 - 3 = 4        {5, 3}
 4 - 4 = 0        {5, 3, 4}

Entonces se puede calcular el otro conjunto: {4,3,10,3,2,5} - {5,3,4} = {10,3,2}

Todos los campos con un número son posibles soluciones para una bolsa. Elija el que está más lejos en la esquina inferior derecha.

Por cierto: Se llama el mochila-problema.

Si todos los pesos (w1, ..., wn y W) son enteros no negativos, la mochila el problema se puede resolver en tiempo pseudo-polinomio usando dinámica programación.

Bueno, se puede encontrar una solución a una precisión porcentual en el tiempo polinomial, pero para encontrar realmente la solución óptima (diferencia mínima absoluta), el problema es NP-completo. Esto significa que no hay solución de tiempo polinómico para el problema. Como resultado, incluso con una lista relativamente pequeña de números, es demasiado intensivo en computación para resolver. Si realmente necesita una solución, eche un vistazo a algunos de los algoritmos de aproximación para esto.

Http://en.wikipedia.org/wiki/Subset_sum_problem

P. Dado un multiset S de enteros, ¿hay una manera de particionar S en dos subconjuntosS1 y S2 de tal manera que la suma de los números en S1 es igual a la suma de los números en S2?

A. Establecer Problema de partición.

La mejor de las suertes aproximando. : )

Tenga en cuenta que también es una heurística y moví el tipo fuera de la función.

 def g(data):
   sums = [0, 0]
   for pair in zip(data[::2], data[1::2]):
     item1, item2 = sorted(pair)
     sums = sorted([sums[0] + item2, sums[1] + item1])
   print sums

data = sorted([2,3,10,5,8,9,7,3,5,2])
g(data)

En realidad es UNA PARTICIÓN, un caso especial de MOCHILA.

Es NP Completo, con algoritmos pseudo-polinómicos dp. El pseudo en pseudo-polinomio se refiere al hecho de que el tiempo de ejecución depende del rango de los pesos.

En general, primero tendrá que decidir si hay una solución exacta antes de poder admitir una solución heurística.

Un caso de prueba donde su método no funciona es

que = [1, 1, 50, 50, 50, 1000]

El problema es que estás analizando cosas en pares, y en este ejemplo, quieres que todos los 50 estén en el mismo grupo. Sin embargo, esto debe resolverse si elimina el aspecto de análisis de pares y solo hace una entrada a la vez.

Aquí está el código que hace esto

def make_teams(que):
    que.sort()
    que.reverse()
    if len(que)%2: que.insert(0,0)
    t1,t2 = [],[]
    while que:
        if abs(len(t1)-len(t2))>=len(que):
            [t1, t2][len(t1)>len(t2)].append(que.pop(0))
        else:
            [t1, t2][sum(t1)>sum(t2)].append(que.pop(0))
    print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)), "\n"

if __name__=="__main__":
    que = [2,3,10,5,8,9,7,3,5,2]
    make_teams(que)
    que = [1, 1, 50, 50, 50, 1000]
    make_teams(que)

Esto da 27, 27 y 150, 1002 que son las respuestas que tienen sentido para mí.

Editar: En la revisión, me parece que esto no en realidad funciona, aunque al final, no estoy muy seguro de por qué. Publicaré mi código de prueba aquí, ya que podría ser útil. La prueba simplemente genera secuencias aleatorias que tienen sumas iguales, las une y las compara (con resultados tristes).

Edit #2: Basado en el ejemplo señalado por Unknown, [87,100,28,67,68,41,67,1], está claro por qué mi método no funciona. Específicamente, para resolver este ejemplo, los dos números más grandes deben agregarse a la misma secuencia para obtener una solución.

def make_sequence():
    """return the sums and the sequence that's devided to make this sum"""
    while 1:
        seq_len = randint(5, 200)
        seq_max = [5, 10, 100, 1000, 1000000][randint(0,4)]
        seqs = [[], []]
        for i in range(seq_len):
            for j in (0, 1):
                seqs[j].append(randint(1, seq_max))
        diff = sum(seqs[0])-sum(seqs[1])
        if abs(diff)>=seq_max: 
            continue
        if diff<0:
            seqs[0][-1] += -diff
        else:
            seqs[1][-1] += diff
        return sum(seqs[0]), sum(seqs[1]), seqs[0], seqs[1]

if __name__=="__main__":

    for i in range(10):
        s0, s1, seq0, seq1 = make_sequence()
        t0, t1 = make_teams(seq0+seq1)
        print s0, s1, t0, t1
        if s0 != t0 or s1 != t1:
            print "FAILURE", s0, s1, t0, t1

Obviamente están buscando una solución de mochila de programación dinámica. Así que después de mi primer esfuerzo (una heurística original bastante buena, pensé), y mi segundo esfuerzo (una solución combinatoria exacta muy astuta que funcionó para conjuntos de datos cortos, e incluso para conjuntos de hasta 100 elementos, siempre y cuando el número de valores únicos fuera bajo), finalmente sucumbí a la presión de los compañeros y escribí el que querían (no demasiado difícil - el manejo de entradas duplicadas el algoritmo subyacente en el que lo basé solo funciona si todas las entradas son únicas - ¡Estoy seguro de que me alegra que long long sea lo suficientemente grande como para contener 50 bits!).

Así que para todos los datos de prueba y los casos extremos incómodos que junté mientras probaba mis dos primeros esfuerzos, da la misma respuesta. Al menos para los que he comprobado con el solucionador combinatorio, yo sé que son correctos. Pero todavía estoy fallando la presentación con alguna respuesta incorrecta!

No estoy pidiendo a nadie que arregle mi código aquí, pero estaría muy agradecido si alguien puede encontrar un caso para el que el código a continuación genera la respuesta incorrecta.

Gracias,

Graham

PS Este código siempre se ejecuta dentro del límite de tiempo, pero está lejos de ser optimizado. lo mantengo simple hasta que pase la prueba, luego tengo algunas ideas para acelerarlo, tal vez por un factor de 10 o más.

#include <stdio.h>

#define TRUE (0==0)
#define FALSE (0!=0)

static int debug = TRUE;

//int simple(const void *a, const void *b) {
//  return *(int *)a - *(int *)b;
//}

int main(int argc, char **argv) {
  int p[101];
  char *s, line[128];
  long long mask, c0[45001], c1[45001];
  int skill, players, target, i, j, tests, total = 0;

  debug = (argc == 2 && argv[1][0] == '-' && argv[1][1] == 'd' && argv[1][2] == '\0');

  s = fgets(line, 127, stdin);
  tests = atoi(s);
  while (tests --> 0) {

    for (i = 0; i < 45001; i++) {c0[i] = 0LL;}

    s = fgets(line, 127, stdin); /* blank line */
    s = fgets(line, 127, stdin); /* no of players */
    players = atoi(s);
    for (i = 0; i < players; i++) {s = fgets(line, 127, stdin); p[i] = atoi(s);}

    if (players == 1) {
      printf("0 %d\n", p[0]);
    } else {

    if (players&1) p[players++] = 0; // odd player fixed by adding a single player of 0 strength
    //qsort(p, players, sizeof(int), simple);

    total = 0; for ( i = 0; i < players; i++) total += p[i];
    target = total/2; // ok if total was odd and result rounded down - teams of n, n+1
    mask = 1LL << (((long long)players/2LL)-1LL);

    for (i = 0; i < players; i++) {
      for (j = 0; j <= target; j++) {c1[j] = 0LL;} // memset would be faster
      skill = p[i];
      //add this player to every other player and every partial subset
      for (j = 0; j <= target-skill; j++) {
        if (c0[j]) c1[j+skill] = c0[j]<<1;  // highest = highest j+skill for later optimising
      }
      c0[skill] |= 1; // so we don't add a skill number to itself unless it occurs more than once
      for (j = 0; j <= target; j++) {c0[j] |= c1[j];}
      if (c0[target]&mask) break; // early return for perfect fit!
    }

    for (i = target; i > 0; i--) {
      if (debug || (c0[i] & mask)) {
        fprintf(stdout, "%d %d\n", i, total-i);
        if (debug) {
          if (c0[i] & mask) printf("******** ["); else
          printf("         [");
          for (j = 0; j <= players; j++) if (c0[i] & (1LL<<(long long)j)) printf(" %d", j+1);
          printf(" ]\n");
        } else break;
      }
    }
    }
    if (tests) printf("\n");
  }
  return 0;
}

class Team(object):
    def __init__(self):
        self.members = []
        self.total = 0

    def add(self, m):
        self.members.append(m)
        self.total += m

    def __cmp__(self, other):
        return cmp(self.total, other.total)


def make_teams(ns):
    ns.sort(reverse = True)
    t1, t2 = Team(), Team()

    for n in ns:
        t = t1 if t1 < t2 else t2
        t.add(n)

    return t1, t2

if __name__ == "__main__":
    import sys
    t1, t2 = make_teams([int(s) for s in sys.argv[1:]])
    print t1.members, sum(t1.members)
    print t2.members, sum(t2.members)

>python two_piles.py 1 50 50 100
[50, 50] 100
[100, 1] 101

Para el rendimiento, guarde los cálculos reemplazando append() y sum() con totales en ejecución.

Puedes apretar tu bucle un poco usando lo siguiente:

def make_teams(que):
    que.sort()
    t1, t2 = []
    while que:
        t1.append(que.pop())
        if sum(t1) > sum(t2):
            t2, t1 = t1, t2
    print min(sum(t1),sum(t2)), max(sum(t1),sum(t2))

Dado que las listas deben ser iguales, el problema no es NP en absoluto.

Divido la lista ordenada con el patrón t1

def make_teams2(que):
    que.sort()
    if len(que)%2: que.insert(0,0)
    t1 = []
    t2 = []
    while que:
        if len(que) > 2:
            t1.append(que.pop(0))
            t1.append(que.pop())
            t2.append(que.pop(0))
            t2.append(que.pop())
        else:
            t1.append(que.pop(0))
            t2.append(que.pop())
    print sum(t1), sum(t2), "\n"

Edit : Supongo que este también es un método incorrecto. Resultados equivocados!

Después de pensar un poco, para un problema no demasiado grande, creo que el mejor tipo de heurística será algo como:

import random
def f(data, nb_iter=20):
  diff = None
  sums = (None, None)
  for _ in xrange(nb_iter):
    random.shuffle(data)
    mid = len(data)/2
    sum1 = sum(data[:mid])
    sum2 = sum(data[mid:])
    if diff is None or abs(sum1 - sum2) < diff:
      sums = (sum1, sum2)
  print sums

Puede ajustar nb_iter si el problema es mayor.

Resuelve todo el problema mencionado anteriormente en su mayoría todas las veces.

En un comentario anterior planteé la hipótesis de que el problema como conjunto era manejable porque habían elegido cuidadosamente los datos de prueba para ser compatibles con varios algoritmos dentro del tiempo asignado. Este no resultó ser el caso - en cambio, es el problema restricciones - números no superiores a 450 y un conjunto final no mayor a 50 números es la clave. Estos son compatibles con resolver el problema utilizando la solución de programación dinámica que puse en un post posterior. Ninguno de los otros algoritmos (heurística, o enumeración exhaustiva por un generador de patrones combinatorios) posiblemente puede funcionar porque habrá casos de prueba lo suficientemente grandes o lo suficientemente duros como para romper esos algoritmos. Es bastante molesto ser honesto porque esas otras soluciones son más desafiantes y ciertamente más divertidas. Tenga en cuenta que sin mucho trabajo adicional, la solución de programación dinámica solo dice si una solución es posible con N/2 para cualquier suma dada, pero no le dice el contenido de ninguna de las particiones.