Algorithmus eine Liste von Zahlen in 2 gleiche Summe Liste an Teilen
https://stackoverflow.com/questions/890171
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Es gibt eine Liste von Zahlen.
Die Liste ist in zwei gleich großen Listen aufgeteilt werden, mit einem minimalen Unterschied in der Summe. Die Summen müssen gedruckt werden.
#Example:
>>>que = [2,3,10,5,8,9,7,3,5,2]
>>>make_teams(que)
27 27
Gibt es einen Fehler in dem folgenden Code-Algorithmus für einigen Fall?
Wie kann ich optimieren und / oder pythonize das?
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"
Die Frage ist von http://www.codechef.com/problems/TEAMSEL/
Lösung
Neue Lösung
Dies ist eine Breitensuche mit Heuristiken Culling. Der Baum wird bis zu einer Tiefe von Spielern begrenzt / 2. Die Spieler Summengrenze totalscores / 2. Mit einem Spieler-Pool von 100, es dauerte etwa 10 Sekunden zu lösen.
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])
Beachten Sie auch, dass ich dies mit GS Beschreibung zu lösen versucht, aber es ist unmöglich, genug Informationen einfach zu erhalten, indem die laufenden Summen zu speichern. Und wenn Sie gespeichert beide die Anzahl der Elemente und Summen, dann wäre es die gleiche wie diese Lösung sein, außer Sie unnötigen Daten gehalten. Da brauchen Sie nur die n-1 und n Iterationen halten bis zu numplayers / 2.
hatte ich einen alten erschöpfende basierend auf Binomialkoeffizienten (Blick in die Geschichte). Es löste das Beispiel Probleme mit der Länge 10 ganz gut, aber dann sah ich, dass der Wettbewerb 100 Personen von bis zu einer Länge hatte.
Andere Tipps
Dynamische Programmierung ist die Lösung, die Sie suchen.
Beispiel mit [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 ist unsere Glückszahl! Rückverfolgung, die Gruppe zu bekommen:
12 - 5 = 7 {5}
7 - 3 = 4 {5, 3}
4 - 4 = 0 {5, 3, 4}
Der andere Satz kann dann berechnet werden: {4,3,10,3,2,5} - {5,3,4} = {10,3,2}
Alle Felder mit einer Reihe Lösungen sind möglich für eine Tasche. Wählen Sie die eine, die am weitesten in der rechten unteren Ecke ist.
BTW: Es ist die Ranzen-Problem genannt
.Wenn alle Gewichte (w1, ..., wn und W) nicht negative ganze Zahlen, die Ranzen Problem kann dadurch gelöst werden, Pseudopolynomiell mit dynamischem Programmierung.
Nun, Sie eine Lösung für eine Prozentsatz Präzision in Polynomzeit finden können, aber finden tatsächlich die optimale (absolut minimale Differenz) Lösung, das Problem ist NP-vollständig. Das bedeutet, dass es keine Polynomzeit Lösung für das Problem ist. Als Ergebnis auch mit einer relativ kleinen Liste von Zahlen, ist es zu intensiv berechnen zu lösen. Wenn Sie wirklich eine Lösung benötigen, werfen Sie einen Blick auf einige der Approximationsalgorithmen für diese.
Q. Bei einem multiset S von ganzen Zahlen , gibt es einen Weg S in zwei Untergruppen S1 und S2, so dass die Summe der Zahlen in S1 zu partitionieren ist gleich der Summe der Zahlen in S2?
Viel Glück annähert. :)
Beachten Sie, dass es auch eine Heuristik ist und ich zog die Art aus der Funktion.
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)
Es ist eigentlich PARTITION, ein Spezialfall von KNAPSACK.
Es ist NP Complete, mit pseudo-Polynom dp Algorithmen. Die Pseudo in pseudo-Polynom bezieht sich auf die Tatsache, dass die Laufzeit auf den Bereich der Gewichte abhängig ist.
In der Regel müssen Sie zunächst entscheiden, ob es eine exakte Lösung ist, bevor Sie eine heuristische Lösung zugeben kann.
Ein Testfall, wo Ihre Methode nicht funktioniert, ist
que = [1, 1, 50, 50, 50, 1000]
Das Problem ist, dass Sie die Dinge in Paaren sind die Analyse, und in diesem Beispiel möchten Sie alle 50ern in der gleichen Gruppe sein. Dies sollte jedoch gelöst werden, wenn Sie das Paar Analyse Aspekt entfernen und gerade in einer Zeit, einen Eintrag tun.
Hier ist der Code, der dies tut,
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)
gibt Dieses 27, 27 und 150, 1002, welche die Antworten sind, der Sinn für mich.
Edit: Im Rückblick finde ich dies nicht wirklich funktionieren, wenn auch am Ende, ich bin mir nicht ganz sicher, warum. Ich werde mein Testcode schreiben hier aber, wie es nützlich sein könnten. Der Test erzeugt nur Zufallssequenz, die gleich Summen hat, diese zusammenstellt und vergleicht (mit traurigen Ergebnissen).
Bearbeiten # 2: im Beispiel Basierend darauf hingewiesen, von Unknown, [87,100,28,67,68,41,67,1], es ist klar, warum meine Methode funktioniert nicht. Insbesondere dieses Beispiel zu lösen, haben die beiden größten Zahlen müssen beide auf die gleiche Sequenz hinzugefügt werden, um eine gültige Lösung zu erhalten.
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
Sie suchen offensichtlich für eine dynamische Programmierung Ranzen Lösung. Also nach meinem ersten Versuch (ein ziemlich gutes original heuristischen dachte ich), und meinen zweiten Versuch (eine wirklich hinterhältig genaue kombinatorische Lösung, die für shortish Datensätze gearbeitet, und auch für Mengen bis zu 100 Elemente, solange die Anzahl des einzigartig Werte niedrig waren), ich erliegen Druck gleiche und schrieben den, der sie (nicht zu hart wollte - Umgang mit duplizierten Einträgen war der schwierigste Teil - der zugrunde liegende Algorithmus ich es basierend auf nur funktioniert, wenn alle Eingänge sind einzigartig - ich bin sicher froh, dass long long groß genug ist, 50 Bits zu halten)
!.Also für alle die Testdaten und unbeholfen Rand Fällen, die ich zusammen, während meine beiden ersten Bemühungen testen, gibt es die gleiche Antwort. Zumindest für die, die ich mit der kombinatorischen Löser geprüft, I wissen sie richtig sind. Aber ich bin immer noch die Vorlage mit einiger falschen Antwort versagt!
Ich frage nicht für jemand meinen Code hier zu beheben, aber ich wäre sehr dankbar, wenn jemand einen Fall, für den finden Sie den Code unten die falsche Antwort erzeugt.
Danke,
Graham
PS ist dieser Code immer innerhalb der Frist ausführen, aber es ist weit von optimiert. Ich halte es einfach, bis er den Test besteht, dann habe ich einige Ideen, um es zu beschleunigen, vielleicht um einen Faktor von 10 oder mehr.
#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
Für Leistung, die Sie Berechnungen sparen durch Anfügen ersetzen () und sum () mit laufenden Summen.
Sie können Ihre Schleife straffen ein wenig durch die folgende Verwendung:
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))
Da die Listen müssen mir gleich das Problem ist NP nicht.
aufgeteilt ich das sortierte Liste mit dem Muster t1 <-que (1, liest), t2 <-que (2., liest-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"
Bearbeiten : Ich nehme an, dass dies auch eine falsche Methode. Falsche Ergebnisse!
Nach einiger Überlegung, für nicht allzu großes Problem, denke ich, dass die beste Art von Heuristik so etwas wie sein:
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
Sie können nb_iter einstellen, wenn das Problem ist größer.
Sie löst das Problem all oben meist alle mal erwähnt.
In einem frühen Kommentar angenommen, ich, dass das Problem als Set lenkbar war, weil sie sorgfältig die Testdaten ausgewählt hatten alloted mit verschiedenen Algorithmen innerhalb der Zeit, kompatibel zu sein. Dies erwies sich als nicht der Fall zu sein - statt es das Problem Zwänge - Zahlen nicht höher als 450 und ein abschließender Satz nicht größer als 50 Zahlen ist der Schlüssel. Diese sind kompatibel mit der Lösung des Problems mit der dynamischen Programmierung Lösung, die ich in einem späteren Beitrag setzen. Keiner der anderen Algorithmen (Heuristik oder erschöpfende Aufzählung von einem kombinatorischen Mustergenerator) kann möglicherweise funktionieren, weil es Testfälle groß genug oder hart genug sein, um diese Algorithmen zu brechen. Es ist ziemlich ärgerlich, um ehrlich zu sein, weil diese anderen Lösungen anspruchsvoller sind und sicherlich mehr Spaß. Beachten Sie, dass ohne viel zusätzliche Arbeit, die dynamische Programmierung Lösung sagt nur, ob eine Lösung mit N / 2 für jede gegebene Summe möglich ist, aber es funktioniert nicht sagen Ihnen, den Inhalt jeder Partition.
