Algorithme de Diviser une liste de nombres dans 2 l'égalité de la somme des listes

Il y a une liste de nombres.

La liste est divisée en 2 de taille égale listes, avec une différence minime dans la somme. Les sommes doivent être imprimés.

#Example:
>>>que = [2,3,10,5,8,9,7,3,5,2]
>>>make_teams(que)
27 27

Est-il une erreur dans le code suivant algorithme pour certains cas?

Comment puis-je optimiser et/ou pythonize ce?

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"

Question est de http://www.codechef.com/problems/TEAMSEL/

  • Est-ce Devoirs?
  • est-ce une variante du bin-packing problème? C'est un problème NP-complet de problème, IIRC.
  • qc = [1,50,50,100] devrait vous donner équipes de 100 et 101. Je pense que votre algorithme rendement de 51 et 150.
  • C'est un problème pratique dans un concours de programmation. Voici la référence: codechef.com/problems/TEAMSEL de Mon mieux comprendre dit, il est de droite. Mais le système marqué cette incorrecte.
  • B: Quand j'ai couru, j'ai eu 100 et 101.
  • B: je reçois 100 et 101, à juste titre, pour votre entrée.
  • regarde ma solution, je pense que vous l'aimerez.