Algorithme pour diviser une liste de nombres en 2 listes de somme égale

La programmation Dynamique est la solution que vous cherchez.

Exemple avec [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 est notre numéro chanceux! Retour en arrière pour obtenir le groupe:

12 - 5 = 7        {5}
 7 - 3 = 4        {5, 3}
 4 - 4 = 0        {5, 3, 4}

L'autre peut alors être calculé: {4,3,10,3,2,5} - {5,3,4} = {10,3,2}

Tous les champs avec un nombre sont des solutions possibles pour un sac. Choisissez celui qui est le plus éloigné dans le coin inférieur droit.

BTW: ça s'appelle le sac-à-dos-problème.

Si tous les poids (w1, ..., wn et W) sont entiers non négatifs, le sac à dos problème peut être résolu en temps pseudo-polynomial utilisant dynamique programmation.

Eh bien, vous pouvez trouver une solution à une précision en pourcentage dans le temps polynomial, mais pour trouver la solution optimale (différence minimale absolue), le problème est NP-complet. Cela signifie qu'il n'y a pas de solution temporelle polynomiale au problème. En conséquence, même avec une liste de nombres relativement petite, il est trop intensif pour calculer à résoudre. Si vous avez vraiment besoin d'une solution, jetez un oeil à certains des algorithmes d'approximation pour cela.

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

Q. étant donné un multiset s d'entiers , Existe-t-il un moyen de partitionner s en deux sous-ensembles S1 et S2 tels que la somme des nombres dans S1 est égale à la somme des nombres dans S2?

A. Régler Le Problème De Partition .

Bonne approximation de chance. : )

Notez que c'est aussi une heuristique et j'ai déplacé le tri de la fonction.

 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)

C'est en fait une PARTITION, un cas particulier de sac à dos.

Il est NP complet, avec des algorithmes dp pseudo-polynomiaux. Le pseudo En pseudo-polynôme fait référence au fait que le temps d'exécution dépend de la plage des poids.

En général, vous devrez d'abord décider s'il existe une solution exacte avant de pouvoir admettre une solution heuristique.

Un cas de test où votre méthode ne fonctionne pas est

que = [1, 1, 50, 50, 50, 1000]

Le problème est que vous analysez les choses par paires, et dans cet exemple, vous voulez que tous les 50 soient dans le même groupe. Cela devrait être résolu si vous supprimez l'aspect d'analyse de paire et faites juste une entrée à la fois.

Voici le code qui fait cela

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)

Cela donne 27, 27 et 150, 1002 qui sont les réponses qui ont du sens pour moi.

Edit: en revue, je trouve que ce n'est pas le cas en fait travailler, mais à la fin, je ne suis pas tout à fait sûr pourquoi. Je vais poster mon code de test ici, car cela pourrait être utile. Le test génère simplement une séquence aléatoire qui a des sommes égales, les rassemble et les compare (avec des résultats tristes).

Edit #2:, Basé dans l'exemple souligné par des Inconnus, [87,100,28,67,68,41,67,1], il est clair pourquoi ma méthode ne fonctionne pas. Plus précisément, pour résoudre cet exemple, les deux plus grands nombres doivent être ajoutés à la même séquence pour obtenir un solution.

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

Ils sont évidemment à la recherche d'une solution de programmation dynamique. Donc, après mon premier effort (une très bonne heuristique originale que je pensais), et mon deuxième effort (une solution combinatoire exacte vraiment sournoise qui fonctionnait pour les ensembles de données shortish, et même pour les ensembles jusqu'à 100 éléments tant que le nombre de unique valeurs était faible), j'ai finalement succombé à la pression des pairs et l'algorithme sous-jacent sur lequel je l'ai basé ne fonctionne que si toutes les entrées sont uniques-je suis sûr que long long est assez grand pour contenir 50 bits!).

Donc, pour toutes les données de test et les cas de bord maladroits que j'ai mis en place en testant mes deux premiers efforts, cela donne la même réponse. Au moins pour ceux que j'ai vérifiés avec le solveur combinatoire, je sais qu'ils sont corrects. Mais j'échoue toujours à la soumission avec une mauvaise réponse!

Je ne demande à personne de réparer mon code ici, mais je serais très heureux si quelqu'un pouvait trouver un cas pour lequel le code ci-dessous génère la mauvaise réponse.

Merci,

Graham

PS CE code s'exécute toujours dans le délai mais il est loin d'être optimisé. je reste simple jusqu'à ce qu'il passe le test, alors j'ai quelques idées pour l'accélérer, peut-être par un facteur de 10 ou plus.

#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

Pour les performances, vous enregistrez les calculs en remplaçant append () et sum () par des totaux en cours d'exécution.

Vous pouvez resserrer un peu votre boucle en utilisant ce qui suit:

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

Puisque les listes doivent être égales, le problème n'est pas du tout NP.

Je divise la liste triée avec le motif t1

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"

Edit: je suppose que c'est aussi une mauvaise méthode. De mauvais résultats!

Après avoir réfléchi, pour un problème pas trop important, je pense que le meilleur type d'heuristique sera quelque chose comme:

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

Vous pouvez ajuster nb_iter si le problème est plus grand.

Il résout tous les problèmes mentionnés ci-dessus la plupart du temps.

Dans un commentaire précédent, j'ai émis l'hypothèse que le problème en tant qu'ensemble était traitable parce qu'ils avaient soigneusement choisi les données de test pour être compatibles avec divers algorithmes dans le temps alloué. Cela s'est avéré ne pas être le cas-au lieu de cela, ce sont les contraintes de problème - des nombres ne dépassant pas 450 et un ensemble final ne dépassant pas 50 nombres est la clé. Ceux-ci sont compatibles avec la résolution du problème en utilisant la solution de programmation dynamique que j'ai mise en place dans un post ultérieur. Aucun des autres algorithmes (heuristiques, ou énumération exhaustive par un générateur de motifs combinatoires) peut éventuellement fonctionner car il y aura des cas de test assez grands ou assez durs pour casser ces algorithmes. C'est plutôt ennuyeux d'être honnête parce que ces autres solutions sont plus difficiles et certainement plus amusantes. Notez que sans beaucoup de travail supplémentaire, la solution de programmation dynamique indique simplement si une solution est possible avec N/2 pour une somme donnée, mais elle ne vous indique pas le contenu de l'une ou l'autre partition.