Algorithme de diviser une liste des numéros en 2 listes de somme égale
https://stackoverflow.com/questions/890171
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Il y a une liste de numéros.
La liste doit être divisée en 2 listes de taille égale, avec une différence minime en somme. Les sommes doivent être imprimées.
#Example:
>>>que = [2,3,10,5,8,9,7,3,5,2]
>>>make_teams(que)
27 27
Y at-il une erreur dans l'algorithme de code suivant pour certains cas?
Comment optimiser et / ou pythonize cela?
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 question est de http://www.codechef.com/problems/TEAMSEL/
La solution
Nouvelle solution
Ceci est une recherche en largeur d'abord avec l'abattage des heuristiques. L'arbre est limitée à une profondeur de joueurs / 2. La limite d'un montant joueur est totalscores / 2. Avec un pool de joueurs de 100, il a fallu environ 10 secondes pour résoudre.
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])
Notez également que j'essayé de résoudre ce en utilisant la description de GS, mais il est impossible d'obtenir suffisamment d'informations simplement en stockant les totaux de fonctionnement. Et si vous stored deux le nombre d'éléments et totaux, alors ce serait la même que cette solution, sauf vous avez conservé des données inutiles. Parce que vous avez seulement besoin de garder le n-1 et n itérations jusqu'à numplayers / 2.
J'avais une ancienne exhaustive basée sur les coefficients binomiaux (regardez dans l'histoire). Il a résolu les problèmes par exemple de longueur 10 très bien, mais j'ai vu que la concurrence avait des gens jusqu'à une longueur de 100.
Autres conseils
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! Pour obtenir le tracé rétrograde groupe:
12 - 5 = 7 {5}
7 - 3 = 4 {5, 3}
4 - 4 = 0 {5, 3, 4}
L'autre ensemble peut alors être calculé: {4,3,10,3,2,5} - {5,3,4} = {} 10,3,2
Tous les champs avec un certain nombre sont des solutions possibles pour un sac. Choisissez celui qui est le plus dans le coin en bas à droite.
BTW: Il appelle les problème-havresac
.Si tous les poids (w1, ..., WN et W) sont des entiers non négatifs, le havresac problème peut être résolu pseudo-polynomiale temps à l'aide dynamique la programmation.
Eh bien, vous pouvez trouver une solution à une précision de pourcentage en temps polynomial, mais pour trouver la solution en fait, le problème optimal (différence minimale absolue) est NP-complet. Cela signifie qu'il n'y a pas de solution polynomiale au problème. Par conséquent, même avec une liste relativement faible de chiffres, 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.
Q. Étant donné un multiset S des nombres entiers , il est un moyen pour partitionner S en deux sous-ensembles S1 et S2 telle que la somme des nombres dans S1 est égale à la somme des nombres dans S2?
Bonne chance approximation. :)
Notez qu'il est aussi une heuristique et je me suis déplacé le genre 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)
Il est en fait PARTITION, un cas particulier de KNAPSACK.
Il est NP complet, avec des algorithmes pseudo-dp polynôme. Le pseudo en pseudo-polynomial fait référence au fait que la durée de fonctionnement dépend de la gamme des poids.
En général, vous devrez d'abord décider s'il y a 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 toutes les années 50 à être dans le même groupe. Cela devrait être résolu que si vous supprimez l'aspect d'analyse de paire et il suffit de faire 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.
Modifier En résumé, je trouve que cela ne fait travailler, mais à la fin, je ne suis pas tout à fait sûr pourquoi. Je vais poster mon code de test ici si, comme il pourrait être utile. Le test génère juste séquence aléatoire qui ont des sommes égales, met ces ensemble et compare (avec des résultats tristes).
Edit # 2: Basé dans l'exemple souligné par Unknown, [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 tous deux être ajouté à la même séquence pour obtenir une solution valable.
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 cherchent évidemment une solution havresac de programmation dynamique. Donc, après mon premier effort (une assez bonne heuristique originale que je pensais), et mon deuxième effort (une solution combinatoire exacte vraiment sournoise qui a travaillé pour des ensembles de données pas trop longues, et même pour les jeux jusqu'à 100 éléments aussi longtemps que le nombre de valeurs uniques était faible), j'ai finalement succombé à la pression des pairs et écrit celui qu'ils voulaient (pas trop dur - la manipulation des entrées en double a été la partie la plus délicate - l'algorithme sous-jacent I basé sur ne fonctionne que si toutes les entrées sont uniques - Je suis sûr heureux que long long est assez grand pour contenir 50 bits)
.Donc, pour toutes les données de test et les cas de pointe difficiles que je mets ensemble tout en testant mes deux premiers efforts, il donne la même réponse. Au moins pour ceux que j'ai vérifié avec le solveur combinatoires, I sais ils sont corrects. Mais je suis toujours à défaut la soumission avec une mauvaise réponse!
Je ne demande pas à quiconque de fixer mon code ici, mais je serais très reconnaissant si quelqu'un peut trouver un cas pour lequel le code ci-dessous génère la mauvaise réponse.
Merci,
Graham
PS Ce code n'exécute toujours dans la limite de temps, mais il est far de optimisé. Je garde simple jusqu'à ce qu'il passe le test, j'ai quelques idées pour 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 des performances que vous enregistrez les calculs en remplaçant append () et somme () avec des totaux de fonctionnement.
Vous pouvez serrer la boucle un peu en utilisant les éléments suivants:
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))
Étant donné que les listes doivent me égalent le problème n'est pas du tout NP.
Je coupais la liste triée avec le motif t1 <-que (1er, dernier), t2 <-que (2, dernier-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"
Modifier : Je suppose que cela est aussi une mauvaise méthode. des résultats erronés!
Après une réflexion, pour le problème pas trop grand, je pense que le meilleur type de heuristiques 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 régler nb_iter si le problème est plus grand.
Il résout tous les problèmes mentionnés ci-dessus pour la plupart tous les temps.
Dans un commentaire plus tôt, j'émis l'hypothèse que le problème ensemble était traitable parce qu'ils avaient soigneusement choisi les données de test pour être compatible avec différents algorithmes dans le temps imparti. Cela n'a pas été le cas - il est plutôt les contraintes du problème - nombres ne dépassant pas 450 et un ensemble final plus de 50 numéros est la clé. Ceux-ci sont compatibles avec la résolution du problème en utilisant la solution de programmation dynamique que je mets dans un poste plus tard. Aucun des autres algorithmes (heuristiques, ou énumération exhaustive par un générateur de modèle combinatoire) peut éventuellement travailler parce qu'il y aura des cas de test assez assez grandes ou difficiles à briser ces algorithmes. Il est plutôt ennuyeux pour être honnête parce que ces autres solutions sont plus difficiles et certainement plus amusant. Notez que, sans beaucoup de travail supplémentaire, la solution de programmation dynamique dit simplement si une solution est possible avec N / 2 pour une somme donnée, mais il ne vous dit pas le contenu de l'une des partitions.
