python como variable - Algoritmo para dividir una lista de números en 2 listas de suma igual




7 Answers

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.

valor el

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/




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.

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




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



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



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))



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.




Related