Algoritmo para dividir una lista de números en 2 listas coincidir con la suma
https://stackoverflow.com/questions/890171
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
No es una lista de números.
La lista es que ser dividido en 2 listas de igual tamaño, con una diferencia mínima en suma. Las sumas tienen que ser impresa.
#Example:
>>>que = [2,3,10,5,8,9,7,3,5,2]
>>>make_teams(que)
27 27
¿Hay un error en el algoritmo siguiente código para algún caso?
¿Cómo puedo optimizar y / o pythonize esto?
def make_teams(que):
que.sort()
if len(que)%2: que.insert(0,0)
t1,t2 = [],[]
while que:
val = (que.pop(), que.pop())
if sum(t1)>sum(t2):
t2.append(val[0])
t1.append(val[1])
else:
t1.append(val[0])
t2.append(val[1])
print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)), "\n"
Solución
Nueva Solución
Esta es una búsqueda en amplitud con la heurística sacrificio. El árbol está limitada a una profundidad de jugadores / 2. El límite de jugadores suma es totalscores / 2. Con un grupo de jugadores de 100, se tardó aproximadamente 10 segundos para resolver.
def team(t):
iterations = range(2, len(t)/2+1)
totalscore = sum(t)
halftotalscore = totalscore/2.0
oldmoves = {}
for p in t:
people_left = t[:]
people_left.remove(p)
oldmoves[p] = people_left
if iterations == []:
solution = min(map(lambda i: (abs(float(i)-halftotalscore), i), oldmoves.keys()))
return (solution[1], sum(oldmoves[solution[1]]), oldmoves[solution[1]])
for n in iterations:
newmoves = {}
for total, roster in oldmoves.iteritems():
for p in roster:
people_left = roster[:]
people_left.remove(p)
newtotal = total+p
if newtotal > halftotalscore: continue
newmoves[newtotal] = people_left
oldmoves = newmoves
solution = min(map(lambda i: (abs(float(i)-halftotalscore), i), oldmoves.keys()))
return (solution[1], sum(oldmoves[solution[1]]), oldmoves[solution[1]])
print team([90,200,100])
print team([2,3,10,5,8,9,7,3,5,2])
print team([1,1,1,1,1,1,1,1,1,9])
print team([87,100,28,67,68,41,67,1])
print team([1, 1, 50, 50, 50, 1000])
#output
#(200, 190, [90, 100])
#(27, 27, [3, 9, 7, 3, 5])
#(5, 13, [1, 1, 1, 1, 9])
#(229, 230, [28, 67, 68, 67])
#(150, 1002, [1, 1, 1000])
También tenga en cuenta que he tratado de resolver este usando la descripción de GS, pero es imposible conseguir suficiente información simplemente almacenando los totales corrientes. Y si ha almacenado ambos el número de elementos y totales, entonces sería el mismo que esta solución excepto usted guardó los datos innecesarios. Debido a que sólo se necesita para mantener el n-1 y n iteraciones hasta numplayers / 2.
Otros consejos
de programación dinámica es la solución que está 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! Un rastreo para obtener el grupo:
12 - 5 = 7 {5}
7 - 3 = 4 {5, 3}
4 - 4 = 0 {5, 3, 4}
El otro conjunto se puede calcular entonces: {4,3,10,3,2,5} - {5,3,4} = {10,3,2}
Todos los campos con un número son las posibles soluciones para una bolsa. Elija el que está más en la esquina inferior derecha.
Por cierto: Se llama los href="http://en.wikipedia.org/wiki/Knapsack_problem" mochila-problema
.Si todos los pesos (w1, ..., wn y W) son enteros no negativos, la mochila problema puede ser resuelto en pseudo-polinomio tiempo utilizando dinámico la programación.
Bueno, se puede encontrar una solución a un porcentaje de precisión en tiempo polinómico, pero en realidad encontrar la óptima (mínima diferencia absoluta) solución, el problema es NP-completo. Esto significa que no existe una solución en tiempo polinomial al problema. Como resultado, incluso con una pequeña lista de los números, es demasiado cálculo intensivo para resolver. Si realmente necesita una solución, echar un vistazo a algunos de los algoritmos de aproximación para esto.
Q. Dado un multiset S de enteros , hay una forma de partición de S en dos subconjuntos S1 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. conjunto de particiones Problema .
Lo mejor de la suerte que se aproxima. :)
Tenga en cuenta que también es una heurística y me movió el tipo 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 PARTICIÓN, un caso especial de la mochila.
Es NP completo, con algoritmos dp seudo-polinomio. El seudo en pseudo-polinomio se refiere al hecho de que el tiempo de ejecución depende del rango de los pesos.
En general, usted tendrá que decidir primero si hay una solución exacta antes de que pueda admitir una solución heurística.
Un caso de prueba, donde el método no funciona es
que = [1, 1, 50, 50, 50, 1000]
El problema es que se está analizando las cosas en pares, y en este ejemplo, desea que todos los años 50 para estar en el mismo grupo. Esto debe ser resuelto, aunque si se quita el aspecto de análisis par y sólo hacer una entrada a la vez.
Este es 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)
Esta dar 27, 27 y 150, 1002, que son las respuestas que tengan sentido para mí.
Editar En revisión, Me parece que esto no funciona realmente, aunque al final, no estoy seguro de por qué. Voy a publicar mi código de prueba aquí, sin embargo, ya que podría ser útil. La prueba simplemente genera secuencia aleatoria que tienen iguales sumas, pone estos juntos y compara (con resultados tristes).
Editar # 2: Basado en el ejemplo señalado por Desconocido, [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 necesitan tanto se añaden a la misma secuencia para obtener una solución válida.
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
Es evidente que están buscando una solución mochila programación dinámica. Así que después de mi primer esfuerzo (una muy buena heurística original, pensé), y mi segundo esfuerzo (una solución combinatoria exacta realmente astuto que trabajó para conjuntos de datos relativamente breves, e incluso para los conjuntos de hasta 100 elementos, siempre y cuando el número de valores únicos fue baja), que finalmente sucumbió a la presión y escribieron la que querían (no demasiado duro - el manejo de las entradas duplicadas fue la parte más difícil - el algoritmo subyacente basé en sólo funciona si todas las entradas son únicos - estoy muy feliz de que mucho, mucho es lo suficientemente grande como para contener 50 bits)
.Así que para todos los datos de prueba y casos extremos incómodas que puse juntos mientras se prueba mis dos primeros esfuerzos, se da la misma respuesta. Al menos para los que he comprobado con el solucionador de combinatoria, I sé son correctos. Pero todavía estoy fallando la presentación con alguna respuesta equivocada!
No estoy pidiendo para que cualquiera pueda arreglar mi código aquí, pero estaría muy agradecido si alguien puede encontrar un caso para el cual el código de abajo genera la respuesta equivocada.
Gracias,
Graham
PS Este código ejecuta siempre dentro del límite de tiempo, pero es ahora desde optimizado. Estoy hacer que sea sencillo hasta que pasa la prueba, entonces 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 obtener un rendimiento a ahorrar cálculos mediante la sustitución de append () y suma () con los totales acumulados.
Se puede apretar el bucle un poco mediante el uso de 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 equivalen a mí el problema no es NP en absoluto.
Me dividir la lista ordenada con el patrón de t1 <-QUE (primero, apellido), t2 <-QUE (segundo, última-1) ...
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"
Editar : supongo que esto también es un método equivocado. resultados erróneos!
Después de pensar un poco, para no demasiado grande problema, 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 más grande.
Se soluciona todo el problema mencionado anteriormente la mayoría de todos los tiempos.
En un comentario anterior que la hipótesis de que el problema como set fue manejable porque habían elegido cuidadosamente los datos de prueba para ser compatible con varios algoritmos dentro del tiempo asignado. Esto resultó no ser el caso - por el contrario es la restricciones del problema - números no superiores a 450 y un conjunto final de no más de 50 números es la clave. Estos son compatibles con la solución del problema usando la solución de programación dinámica que puse en un post más adelante. Ninguno de los otros algoritmos (heurística, o enumeración exhaustiva por un generador de patrones de combinatoria) posiblemente puede trabajar porque habrá casos de prueba lo suficientemente grandes o duras suficiente para romper esos algoritmos. Es bastante molesto para ser honesto, porque esas otras soluciones son más difíciles y sin duda más divertido. Tenga en cuenta que sin una gran cantidad de trabajo extra, la solución de programación dinámica se limita a decir si una solución es posible con N / 2 para cualquier cantidad dada, pero no le dice a los contenidos de cualquiera de las particiones.
