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




sacar elementos de una lista python (10)

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

https://code.i-harness.com

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!


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.


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.


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

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




knapsack-problem