python - valor - Algoritmo para dividir una lista de números en 2 listas de suma igual
recorrer una lista al reves python (14)
Bueno, puede encontrar una solución a un porcentaje de precisión 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 una solución de tiempo polinomial para el problema. Como resultado, incluso con una lista relativamente pequeña de números, es demasiado computacional para resolver. Si realmente necesita una solución, eche un vistazo a algunos de los algoritmos de aproximación para esto.
Hay una lista de números.
La lista se dividirá en 2 listas del mismo tamaño, con una diferencia mínima en la suma. Las sumas tienen que ser impresas.
#Example:
>>>que = [2,3,10,5,8,9,7,3,5,2]
>>>make_teams(que)
27 27
¿Hay algún error en el siguiente algoritmo de código para algún caso?
¿Cómo optimizo 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"
La pregunta es de http://www.codechef.com/problems/TEAMSEL/
Dado que las listas deben ser iguales, el problema no es NP en absoluto.
Divido la lista ordenada con el patrón t1 <-que (primero, último), t2 <-que (segundo, último-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"
Edición : Supongo que esto también es un método incorrecto. ¡Resultados erróneos!
Después de pensar un poco, no por un problema 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
Puedes ajustar nb_iter si el problema es mayor.
Resuelve todos los problemas mencionados anteriormente, principalmente todos los tiempos.
En realidad es PARTICIÓN, un caso especial de KNAPSACK.
Es NP Completo, con algoritmos pseudo-polinomiales 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.
En un comentario anterior, formulé la hipótesis de que el problema tal como estaba establecido era manejable porque habían elegido cuidadosamente los datos de prueba para que fueran compatibles con varios algoritmos dentro del tiempo asignado. Esto resultó no ser el caso, sino las limitaciones del problema, los números que no superan los 450 y un conjunto final que no supera los 50 números es la clave. Estos son compatibles para resolver el problema usando la solución de programación dinámica que puse en una publicación posterior. Ninguno de los otros algoritmos (heurística, o enumeración exhaustiva por un generador de patrones combinatorios) puede funcionar porque habrá casos de prueba lo suficientemente grandes o lo suficientemente fuertes 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 simplemente dice si una solución es posible con N / 2 para una suma determinada, pero no le informa el contenido de ninguna de las particiones.
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 que el número de valores únicos fuera bajo), finalmente sucumbí a la presión de los compañeros y escribí la que querían (no demasiado difícil: el manejo de las entradas duplicadas fue la parte más difícil; el algoritmo subyacente en el que se basa solo funciona si todas las entradas son únicas; estoy seguro de que largo es lo suficientemente grande como para contener 50 bits!).
Entonces, para todos los datos de prueba y los casos incómodos que reuní al probar mis dos primeros esfuerzos, da la misma respuesta. Al menos para los que consulté con el solucionador combinatorio, sé que son correctos. ¡Pero todavía estoy fallando la presentación con alguna respuesta incorrecta!
No le estoy pidiendo a nadie que arregle mi código aquí, pero sería muy agradecido si alguien pudiera encontrar un caso en el que el siguiente código genere la respuesta incorrecta.
Gracias,
Graham
PS Este código siempre se ejecuta dentro del límite de tiempo, pero está lejos de estar optimizado. Lo mantengo simple hasta que pasa 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; }
P. Dado un conjunto múltiple de S de enteros , ¿hay una manera de dividir S en dos subconjuntos S1 y S2 de tal manera que la suma de los números en S1 sea igual a la suma de los números en S2?
A. Establecer problema de partición .
La mejor de las suertes se acerca. :)
Para el rendimiento, se guardan los cálculos reemplazando append () y sum () con totales acumulados.
Podría apretar un poco su bucle utilizando 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))
Tenga en cuenta que también es una heurística y que eliminé el tipo de 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)
Un caso de prueba donde tu 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. Esto debería resolverse, sin embargo, 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í.
Edit: En revisión, encuentro que esto no funciona, aunque al final, no estoy muy seguro de por qué. Voy a publicar mi código de prueba aquí, ya que podría ser útil. La prueba solo genera una secuencia aleatoria que tiene sumas iguales, las pone juntas y las compara (con resultados tristes).
Edición # 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 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
La programación dinámica 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 numero de la suerte! Backtracing 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: {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.
BTW: Se llama el knapsack-problem la knapsack-problem .
Si todos los pesos (w1, ..., wn y W) son enteros no negativos, el problema de la mochila se puede resolver en tiempo pseudo-polinomial utilizando la programación dinámica.
Nueva solucion
Esta es una búsqueda de amplitud en primer lugar con la selección heurística. El árbol está limitado a una profundidad de jugadores / 2. El límite de la suma del jugador es total de puntuaciones / 2. Con un grupo de 100 jugadores, tardó aproximadamente 10 segundos en resolverse.
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 intenté resolver esto utilizando la descripción de GS, pero es imposible obtener suficiente información simplemente almacenando los totales acumulados. Y si almacena tanto el número de elementos como los totales, entonces sería el mismo que para esta solución, excepto que guardó datos innecesarios. Porque solo necesitas mantener las n-1 yn iteraciones hasta numplayers / 2.
Tenía un antiguo exhaustivo basado en coeficientes binomiales (ver en la historia). Resolvió los problemas de ejemplo de longitud 10 muy bien, pero luego vi que la competencia tenía gente de hasta 100 personas.
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