Algorithmus zum Aufteilen einer Liste von Zahlen in 2 gleiche Summenlisten

Gibt es eine Liste von zahlen.

Die Liste ist aufgeteilt in 2 gleich große Listen, mit einem minimalen Unterschied in der Summe. Die Summen ausgedruckt werden.

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

Ist es ein Fehler im folgenden code-Algorithmus für einen Fall?

Wie kann ich optimieren und/oder pythonize?

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"

Frage ist von http://www.codechef.com/problems/TEAMSEL/

InformationsquelleAutor der Frage Lakshman Prasad | 2009-05-20

Neue Lösung

Dies ist eine Breite-zuerst-Suche mit Heuristiken, die culling. Der Baum ist begrenzt bis zu einer Tiefe von Spieler/2. Der Spieler Summe limit ist totalscores/2. Mit einem Spieler-pool 100, dauerte es ungefähr 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 versuchte, dies zu lösen, mit GS s Beschreibung, aber es ist unmöglich, genügend Informationen einfach, indem die Gesamtsummen. Und wenn Sie gespeichert beide die Anzahl der Elemente und der Summen, dann es wäre das gleiche, als diese Lösung, außer Sie gehalten unnötig Daten. Weil Sie nur benötigen, um die n-1 und n-Iterationen bis zu numplayers/2.

Hatte ich eine alte erschöpfend basiert auf binomial-Koeffizienten (Blick in die Geschichte). Es löste das Beispiel Probleme mit der Länge 10 ganz gut, aber dann sah ich, dass der Wettbewerb mussten die Menschen bis zu der Länge 100.

InformationsquelleAutor der Antwort Unknown

Dynamische Programmierung ist die Lösung, die Sie suchen.

Beispiel mit [4, 3, 10, 3, 2, 5]:

X-Achse: Erreichbar Summe der Gruppe. max = sum(alle zahlen) /2 (aufgerundet) 
Y-Achse: Anzahl Elemente in der Gruppe. max = count-zahlen /2 (aufgerundet) 

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! Backtracing, um die Gruppe:

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

Der andere kann dann berechnet werden,: {4,3,10,3,2,5} - {5,3,4} = {10,3,2}

Alle Felder mit einer Zahl sind mögliche Lösungen für eine Tasche. Wählen Sie die eins, die am weitesten in der unteren rechten Ecke.

BTW: Es heißt, die knapsack-problem.

Wenn alle GEWICHTE (w1, ..., wn und W) sind
nicht-negative ganze zahlen, den Ranzen
problem kann gelöst werden, in
pseudo-polynomialer Zeit durch dynamische
die Programmierung.

InformationsquelleAutor der Antwort Georg Schölly

2

Gut, Sie können eine Lösung finden, um eine prozentuale Genauigkeit in polynomialer Zeit, aber tatsächlich finden die optimale (absoluter minimaler Unterschied) Lösung, das problem ist NP-vollständig. Dies bedeutet, dass es keinen polynomialzeit-Lösung für das problem. Als Ergebnis, auch mit einer relativ kleinen Liste von zahlen, es ist zu Rechen-intensiv zu lösen. Wenn Sie wirklich brauchen eine Lösung, nehmen Sie einen Blick auf einige der approximation algorithmen für diese.

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

InformationsquelleAutor der Antwort Sean Turner
2

F. Gegeben multiset S von ganzen zahlengibt es eine Möglichkeit, die partition S in zwei Teilmengen S1 und S2, so dass die Summe der zahlen in S1 gleich der Summe der zahlen in S2?

A.Set Partition Problem.

Viel Glück heranführen. : )

InformationsquelleAutor der Antwort unj2

Beachten Sie, dass es auch einen heuristischen und ich zog die Art aus der Funktion heraus.

 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)

InformationsquelleAutor der Antwort odwl

1

Es ist eigentlich PARTITION, ein Spezialfall von KNAPSACK.

Ist es NP-Vollständige, mit pseudo-Polynom dp-algorithmen. Die pseudo in pseudo-polynomialer bezieht sich auf die Tatsache, dass die Laufzeit hängt von der Auswahl der GEWICHTE.

Im Allgemeinen müssen Sie zunächst entscheiden, ob es eine exakte Lösung zu finden, bevor Sie zugeben, eine heuristische Lösung.

InformationsquelleAutor der Antwort klochner

Einen Testfall, wo Ihre Methode nicht funktioniert, ist

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

Das problem ist, dass Sie analysieren die Dinge in Paaren, und in dieses Beispiel, Sie wollen alle den 50er Jahren in der gleichen Gruppe. Dieses sollte gelöst werden, obwohl, wenn Sie entfernen Sie die pair-Analyse Aspekt und mache nur einen Eintrag.

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)

Diese geben 27 -, 27-und 150, 1002, das sind die Antworten, die für mich Sinn machen.

Edit: Im Rückblick finde ich, dass dies nicht wirklich funktionieren, aber am Ende, ich bin mir nicht ganz sicher, warum. Ich werde nach meinem test code hier, aber, wie könnte es nützlich sein. Der test erzeugt zufällige Sequenz, die haben die gleichen Summen, setzt diese zusammen und vergleicht (mit den traurigen Ergebnissen).

Edit #2: Sitz in der Beispiel darauf hingewiesen, von Unbekannten, [87,100,28,67,68,41,67,1] es ist klar, warum meine Methode nicht funktioniert. Speziell, um dieses Problem zu lösen. B. die zwei größten zahlen müssen Hinzugefügt werden, um die gleiche Reihenfolge, um eine gültige Lösung.

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

InformationsquelleAutor der Antwort tom10

Offenbar sind Sie auf der Suche für eine dynamische Programmierung Rucksack-Lösung. So, nachdem mein Erster Versuch (einen ziemlich guten original-Heuristik dachte ich), und mein zweiter Versuch (eine wirklich hinterhältige exakte kombinatorische Lösung, arbeitete für kurz-Daten-sets, und sogar für Mengen bis zu 100 Elemente, solange die Anzahl der einzigartige Werte niedrig war) Ich erlag schließlich dem Gruppendruck und schrieb die eine, die Sie wollten (nicht zu hart - Handhabung von duplizierten Einträgen war der schwierigste Teil - die zugrunde liegenden algorithmen I basiert es auf funktioniert nur, wenn alle Eingaben eindeutig sind - ich bin sicher froh, dass lange ist groß genug für 50 bits!).

Also für alle test-Daten und umständlich Rand Fälle, die ich zusammen beim testen meine ersten zwei versuche, es gibt die gleiche Antwort. Zumindest für die, die ich überprüft, die mit der kombinatorischen solver, ich wissen sind Sie richtig. Aber ich bin mir noch immer nicht, die Vorlage mit einigen falschen Antworten!

Ich verlange nicht für jeden fix meinen code hier, aber ich wäre sehr dankbar wenn sich jemand finden können, ein Fall, für den der code unten erzeugt die falsche Antwort.

Dank,

Graham

PS Dieser code wird immer ausgeführt, innerhalb der Frist, aber es ist weit aus optimiert. ich bin es einfach zu halten, bis der test bestanden, dann habe ich ein paar Ideen, um ihn zu beschleunigen, vielleicht um einen Faktor 10 oder mehr.

#include <stdio.h> 

#define TRUE (0==0) 
#define FALSE (0!=0) 

static int debug = TRUE; 

//int einfach(const void *a, const void *b) { 
//return *(int *)a - *(int *)b; 
//} 

int main(int argc, char **argv) { 
int p[101]; 
char *s, line[128]; 
lange, lange Maske, c0[45001], c1[45001]; 
int skill, Spieler, Gegner, i, j, tests, Gesamt = 0; 

debug = (argc == 2 && argv[1][0] == '-' && argv[1][1] == 'd' && argv[1][2] == '\0'); 

s = fgets(line, 127, stdin); 
tests = atoi(s); 
während des (tests --> 0) { 

for (i = 0; i < 45001; i++) {c0[i] = 0LL;} 

s = fgets(line, 127, stdin); /* Leerzeile */
s = fgets(line, 127, stdin); /* Anzahl der Spieler */
Spieler = atoi(s); 
for (i = 0; i < Spieler; i++) {s = fgets(line, 127, stdin); p[i] = atoi(s);} 

if (Spieler == 1) { 
printf("0 %d\n", p[0]); 
} else { 

if (Spieler&1) p[Spieler++] = 0; //ungerade-player behoben, indem ein single-player-0 Stärke 
//qsort(p, Spieler, sizeof(int), simple); 

Summe = 0; for ( i = 0; i < Spieler; i++) Summe += p[i]; 
target = Summe/2; //ok, wenn Sie total seltsam war und das Ergebnis abgerundet - teams von n, n+1 
Maske = 1LL << (((long long)Spieler/2LL)-1LL); 

for (i = 0; i < Spieler; i++) { 
for (j = 0; j <= Ziel; j++) {c1[j] = 0LL;} //memset wäre schneller 
skill = p[i]; 
//fügen Sie diese Spieler zu jedem anderen Spieler und jeder Teilmenge 
for (j = 0; j <= Ziel-Fähigkeiten; j++) { 
if (c0[j]) c1[j+skill] = c0[j]<<1; //highest = höchste j+Fertigkeit für die spätere Optimierung 
} 
c0 [- Fertigkeit] |= 1; //damit wir nicht noch eine Fertigkeit, die Zahl zu sich selbst, es sei denn, es tritt mehr als einmal 
for (j = 0; j <= Ziel; j++) {c0[j] |= c1[j];} 
wenn (c0, [Ziel]&Maske) break; //vorzeitiger Rückgabe für die perfekte Passform! 
} 

for (i = Ziel; i > 0; i--) { 
if (debug || (c0[i] & mask)) { 
fprintf(stdout, "%d %d\n", i, Summe-i); 
if (debug) { 
if (c0[i] & Maske) printf("******** ["); sonst 
printf(" ["); 
for (j = 0; j <= Spieler; j++) if (c0[i] & (1LL<<(long, long)j)) printf(" %d", j+1); 
printf(" ]\n"); 
} else break; 
} 
} 
} 
wenn (tests) printf("\n"); 
} 
return 0; 
}

InformationsquelleAutor der Antwort Graham Toal

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

InformationsquelleAutor der Antwort Aaron Maenpaa

0

Für die Leistung, die Sie speichern, Berechnungen durch ersetzen von append() und Summe() mit den Gesamtsummen.

InformationsquelleAutor der Antwort Glenn

Konnten Sie ziehen Sie die Schleife bis ein wenig mithilfe der folgenden:

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

InformationsquelleAutor der Antwort leif

Da die Listen muss mir gleich das problem nicht NP überhaupt.

Aufgeteilt ich die sortierte Liste mit dem Muster t1<-que(1., Letzte), t2<-que(2., last-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!

InformationsquelleAutor der Antwort Nick Dandoulakis

Nach einiger überlegung für nicht allzu großes problem, ich denke, dass die beste Art von Heuristiken wird so etwas wie:

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

Können Sie einstellen, nb_iter wenn das problem größer ist.

Es löst das oben erwähnte problem meist alle mal.

InformationsquelleAutor der Antwort odwl

0

In einem früheren Kommentar habe ich die Hypothese aufgestellt, dass das problem wie war lenksam, weil Sie hatte sorgfältig ausgewählten Testdaten, um die Kompatibilität mit verschiedenen algorithmen in der Zeit alloted. Es stellte sich heraus nicht der Fall zu sein - stattdessen ist es die problem-Einschränkungen - zahlen nicht höher als 450, und eine Letzte Gruppe, die nicht größer als 50 zahlen ist der Schlüssel. Diese sind kompatibel mit der Lösung des Problems mit Hilfe der dynamischen Programmierung Lösung, die ich in einem späteren post. Keiner der anderen algorithmen (Heuristiken, oder abschliessende Aufzählung durch eine kombinatorische Muster generator) kann möglicherweise funktionieren, denn es werden Testfälle groß genug oder hart genug zu brechen diese algorithmen. Es ist ziemlich nervig um ehrlich zu sein, weil die anderen Lösungen sind mehr herausfordernden und sicherlich mehr Spaß. Beachten Sie, dass ohne eine Menge zusätzlicher Arbeit, die dynamische Programmierung Lösung sagt nur, ob eine Lösung möglich ist, mit N/2 für eine gegebene Summe, aber es sagt Ihnen nicht, den Inhalt entweder partition.

InformationsquelleAutor der Antwort Graham Toal

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.