kleine Aufgabe, Diebe und Beute [HILFE]
-
Bestimmt nicht der beste Ansatz, aber einer bei dem etwas rauskommt:
Du "gibst" Dieb 1 das erste Teil der Beute und danach Dieb2 solange andere Teile aus der Liste bis er mehr oder gleichviel hat. Dann gibts Du Dieb1 wieder solange etwas, bis er mehr hat als Dieb2. Dann ist wieder Dieb2 dran ...Am Ende der Liste lässt Du dir das Ergebnis anzeigen
Danach verschiebst Du das erste Element der Liste ans Ende und lässt den Algorythmus erneut ablaufen. Das machst Du solange bis jedes Element mal das Erste war.
(Eigentlich kein Bruteforce, da dann auch jedes Element bei jedem anderem ersten Element einmal das zweite, dritte, vierte, usw. Element der Liste sein müsste. Das gibt aber bei 10 Elementen eine ziemlich lange Liste an möglichen Permutationen)
-
wwlFraggeR schrieb:
finde leider nix unter partition problem....
kann mir jemand vielleicht bei nem brute force ansatz helfen.. hab in der richtung noch nix gemacht, aber beherrsche so ziemlich alle grundlagen
Schaumal unter Rucksack-Problem.
http://de.wikipedia.org/wiki/Rucksack-Problem
-
Wenn die Beute aufgeteilt wird, haben die Stücke immer nur zwei Zustände: entweder bei Dieb1 oder bei Dieb2. Das reduziert das Problem auf ein binäres.
Da es 10 Beutestücke sind, gibt es also 2^10=1024 Möglichkeiten der Verteilung. Wenn man die 10 Bit als Zahl darstellt, bzw. umgekehrt, kann man eine For-Schleife zum Prüfen aller Möglichkeiten verwenden:nummer binär dieb1 dieb2 0 0000000000 0 alles 1 0000000001 [1] alles-[1] 2 0000000010 [2] alles-[2] 3 0000000011 [1]+[2] alles-[1]-[2] ... 682 1010101010 [2]+[4]+[6]+[8]+[10] [1]+[3]+[5]+[7]+[9] ... 1021 1111111101 alles-[2] [2] 1022 1111111110 alles-[1] [1] 1023 1111111111 alles 0
-
siehe auch "Permutation"
-
Pumeluk2 schrieb:
Bestimmt nicht der beste Ansatz, aber einer bei dem etwas rauskommt:
Du "gibst" Dieb 1 das erste Teil der Beute und danach Dieb2 solange andere Teile aus der Liste bis er mehr oder gleichviel hat. Dann gibts Du Dieb1 wieder solange etwas, bis er mehr hat als Dieb2. Dann ist wieder Dieb2 dran ...Am Ende der Liste lässt Du dir das Ergebnis anzeigen
Find ich gar nicht so schlecht. Ich würde nur davor die Liste sortieren und mit dem größten beginnen, dann gibt es imo das beste Ergebniss.
-
Es gibt den nützlichen Algorithmus next_permutation in der STL. Den lässt du einfach in einer while-Schleife durchlaufen, teilst dein Array in der Mitte auf, summierst die einzelnen Teilbeträge, subtrahierst die Summen und merkst dir den kleinsten Betrag, der ist dann die Beste Lösung.
Das iss reines Brute-Force, braucht O(n!) iterationen, geht bestimmt auch intelligenter.
http://www.sgi.com/tech/stl/next_permutation.html
//edit
Huch, ganz so einfach isses nicht weil die Diebe eine beliebige Anzahl an Stücken bekommen können. Da musste noch in einer inneren Schleife das Array an allen möglichen Positionen teilen und dann testen.
Wobei als Optimierung eine Teilung 0-10 und 10-0 ... übersprungen werden kann.Frage:
Iss dann iss die Komplexität O(n!*n+1) ?
-
HIRSCH_H schrieb:
Iss dann iss die Komplexität O(n!*n+1) ?
Sowas gibt's nicht (wirklich). O(n + 1) = O(n), daher ist das obige in jedem Fall O(n!).
Abgesehen davon ist die Komplexitätsklasse soweit ich das sehe "nur" O(2^n).
-
Konrad Rudolph schrieb:
HIRSCH_H schrieb:
Iss dann iss die Komplexität O(n!*n+1) ?
Sowas gibt's nicht (wirklich). O(n + 1) = O(n), daher ist das obige in jedem Fall O(n!).
Abgesehen davon ist die Komplexitätsklasse soweit ich das sehe "nur" O(2^n).Meinte auch O(n!*(n+1)). Die Permutation hat doch die Komplexität n! hinzu kommt die innere Schleife für das Verschieben der Grenzen wobei es n+1 Möglichkeiten gibt. Wie kommst du auf O(2^n)?
-
Wenn du das so siehst, dann kannst du das doch weiter aufdröseln: n!*(n+1) = (n+1)! = O(n!).
(und afaik kann man die Fakultät auch durch eine Exponentialfunktion abschätzen)
-
(n+1)! liegt in O(n!)? Das glaube ich nicht. Gib mal ne Konstante an, sodaß n! für alle n (n+1)! dominiert. Das geht nämlich nicht, sobald n+1 über Deine Konstante wächst wird (n+1)! größer als Konstante*n!. => O(n!) != O((n+1)!)
@Konrad Rudolph:
Die Komplexität von was ist "nur" O(2^n)? Die des Problems? Falls ja, würde mich die Begründung dazu interessieren. Du wärst damit ner ganz heißen Sache auf der Spur.
-
siehe mein Post
Hier geht's nicht um Permutationen sondern rein um Verteilung. Wie die Teile sortiert sind, interessiert hier nicht.
