Hallo, ich suche einen Algorithmus mit möglichst günstiger Laufzeit. Der Algorithmus soll in meta template programming implementiert werden, von daher wäre ein möglichst einfacher Algorithmus schön. Der Algorithmus soll eine bestimmte Menge von Elementen auf ein oder zwei Listen aufteilen. Jedes Element hat eine bestimmte Länge, die Summe der Längen aller Listen-Elemente darf die feste Maximal-Länge einer Liste nicht überschreiten. Wenn nur eine Liste nötig ist, um alle Element aufzunehmen, dann sollte der Algorithmus diese Lösung finden und bevorzugen (Wahrscheinlich ist es da am einfachsten mal die Summe über alle Elemente zu bilden). Sind eh zwei Listen nötig, spielt der Füllgrad der Listen keine Rolle. Beispiel: Maximale-Listen-Länge: 32 Elemente: 7, 7, 22, 6, 4, 18 Lösung: Liste1: 7, 7, 18 (Summe = 32) Liste2: 22, 6, 4 (Summe = 32) Hat jemand 'ne gute Idee? mfg und schönen Dank im Voraus Torsten
Torsten R. schrieb: > Wenn nur eine Liste nötig ist, um alle > Element aufzunehmen, dann sollte der Algorithmus diese Lösung finden Torsten R. schrieb: > Sind eh zwei Listen nötig, spielt der Füllgrad > der Listen keine Rolle. Dann füll doch erst die eine und wenn die voll ist die andere.
Das ganze ist unter dem Namen "Bin Packing" oder Behaelterproblem bekannt. (einziger Unterschied: die Anzahl der Behaelter ist konstant, bei Dir nicht) Die optimale Loesung ist wohl nur mit Rechenaufwand zu finden ("durchprobieren"). Es gibt aber ein paar gute Approximationen, siehe: https://de.wikipedia.org/wiki/Beh%C3%A4lterproblem zigzeg
Man könnte so vorgehen, dass man aus der Menge von Elementen eine Teilmenge so ermittelt, dass die Summe ihrer Elemente maximal, aber höchstens 32 ist. Diese Elemente packt man in die erste Ergebnisliste, für den Rest wird das Vorgehen wiederholt bis alle Elemente aufgebraucht sind. Sind die Elemente ganzzahlig und positiv? Wenn ja, liefert der folgende Algorithmus eine optimale Teilmenge zur Befüllung der ersten Ergebnisliste:
1 | #include <stdio.h> |
2 | #include <stdlib.h> |
3 | |
4 | #define MAXLEN 32
|
5 | |
6 | int main(int argc, char *argv[]) { |
7 | static int lastelement[MAXLEN+1]; |
8 | |
9 | // Ermittlung einer Teilmenge der Elemente, deren Summe möglichst
|
10 | // nah bei MAXLEN liegt, diesen Wert aber nicht überschreitet
|
11 | |
12 | lastelement[0] = -1; |
13 | for(int i=1; i<argc; i++) { |
14 | int el = atoi(argv[i]); |
15 | for(int len=MAXLEN; len>=0; len--) { |
16 | if(lastelement[len]) { |
17 | int sum = len + el; |
18 | if(sum<=MAXLEN && lastelement[sum]==0) |
19 | lastelement[sum] = el; |
20 | }
|
21 | }
|
22 | }
|
23 | |
24 | // Ausgabe der gefundenen Elemente
|
25 | |
26 | int len = MAXLEN; |
27 | while(lastelement[len] == 0) |
28 | len--; |
29 | printf("Genutzte Gesamtlänge: %d von %d\n", len, MAXLEN); |
30 | while(len) { |
31 | int el = lastelement[len]; |
32 | printf("%d ", el); |
33 | len -= el; |
34 | }
|
35 | printf("\n"); |
36 | |
37 | return 0; |
38 | }
|
Der Algorithmus basiert auf dem Prinzip der dynamischen Programmierung und wird O(n·m) abgearbeitet, wenn n die Anzahl der Elemente und m die maximale Summe der Ergebnisliste (hier 32) ist. Bei fest vorgegebener maximaler Summe hat der Algorithmus also lineare Laufzeit. Beispiel 1: Die Summe von 32 kann exakt erreicht werden:
1 | $ pack 7 7 22 6 4 18 |
2 | Genutzte Gesamtlänge: 32 von 32 |
3 | 4 6 22 |
Beispiel 2: Die Summe von 32 kann nicht erreicht werden, die maximal mögliche Summe ist 30:
1 | $ pack 1 6 10 5 18 |
2 | Genutzte Gesamtlänge: 30 von 32 |
3 | 18 5 6 1 |
:
Bearbeitet durch Moderator
Und die Aufteilung auf die anderen Container? ;-) Das Bin-Packing Problem kommt dem schon ziemlich nah. Und da eine Mischung aus FirstFit und HighFirst.
Draco schrieb: > Und die Aufteilung auf die anderen Container? ;-) Das habe ich jetzt nicht ausprogrammiert, das Prinzip ist aber einfach: Nach dem erste Durchlauf entfernt man die bereits genutzten Elemente aus der Menge und startet den Algorithmus mit der Restmenge erneut. Beispiel (mit manueller Entfernung der genutzten Elemente ;-)):
1 | $ pack 3 5 13 10 6 7 15 24 14 9 11 |
2 | Genutzte Gesamtlänge: 32 von 32 |
3 | 6 10 13 3 |
4 | |
5 | $ pack 5 7 15 24 14 9 11 # die Elemente 6, 10, 13 und 3 aus dem ersten |
6 | # Durchlauf fallen weg |
7 | Genutzte Gesamtlänge: 32 von 32 |
8 | 11 14 7 |
9 | |
10 | $ pack 5 15 24 9 |
11 | Genutzte Gesamtlänge: 29 von 32 |
12 | 24 5 |
13 | $ pack 15 9 |
14 | |
15 | Genutzte Gesamtlänge: 24 von 32 |
16 | 9 15 |
Damit sind alle Elemente aufgebraucht. Zwei der Container konnten komplett gefüllt werden, die beiden anderen nicht ganz. Mehr ist aber auch mit einer anderen Auswahl der Elemente nicht möglich.
Torsten R. schrieb: > Der Algorithmus soll eine bestimmte Menge von Elementen auf ein oder > zwei Listen aufteilen. Jedes Element hat eine bestimmte Länge, die Summe > der Längen aller Listen-Elemente darf die feste Maximal-Länge einer > Liste nicht überschreiten. Wenn nur eine Liste nötig ist, um alle > Element aufzunehmen, dann sollte der Algorithmus diese Lösung finden und > bevorzugen (Wahrscheinlich ist es da am einfachsten mal die Summe über > alle Elemente zu bilden). Sind eh zwei Listen nötig, spielt der Füllgrad > der Listen keine Rolle. Der Algorithmus ist bei diesen Anforderungen doch ganz einfach: Elementsumme feststellen Gucken, ob's in eine Liste passt Wenn ja, pack's in eine Liste Wenn nein: fülle eine Liste, bis nächstes Element nicht mehr reinpasst fülle Rest in zweite Liste Das ist so trivial, da rollen sich einem bei dem Gedanken, dass für dieses Problem irgendwer, der sich für einen Programmierer hält, die Lösung erfragen muss, doch gelinde die Zehennägel hoch... Ich befürchte aber, dass es viel schlimemr ist: Du hast vermutlich nicht einmal die Anforderungen korrekt verstanden bzw. hier korrekt dargestellt...
Torsten R. schrieb: > ich suche einen Algorithmus mit möglichst günstiger Laufzeit. Der > Algorithmus soll in meta template programming implementiert werden, von > daher wäre ein möglichst einfacher Algorithmus schön. Algorithmen haben es so an sich, dass sie von einer konkreten Implementierung völlig unabhängig sind.
c-hater schrieb: > Der Algorithmus ist bei diesen Anforderungen doch ganz einfach: > > Elementsumme feststellen > Gucken, ob's in eine Liste passt > Wenn ja, pack's in eine Liste > Wenn nein: > fülle eine Liste, bis nächstes Element nicht mehr reinpasst > fülle Rest in zweite Liste Mit dem ersten Beispiel 7, 7, 22, 6, 4, 18 ergibt das Liste 1: 7, 7, 6, 4 Liste 2: 22 Liste 3: 18 Nicht optimal.
c-hater schrieb: > Das ist so trivial, da rollen sich einem bei dem Gedanken, dass für > dieses Problem irgendwer, der sich für einen Programmierer hält, die > Lösung erfragen muss, doch gelinde die Zehennägel hoch... Tja und wenn man nur ein Programmierer ist versagt man grandios bei dieser Aufgabe wie du eindrucksvoll bewiesen hast. Tja es gibt halt nen Unterschied zwischen Hobbycodern und ausgebildeten Fachkräften.
Josef schrieb: > Mit dem ersten Beispiel 7, 7, 22, 6, 4, 18 > ergibt das > > Liste 1: 7, 7, 6, 4 > Liste 2: 22 > Liste 3: 18 > > Nicht optimal. Wieso sollte das nicht optimal sein? Jedenfalls im Sinne des von dir selber geposten Anforderungswerks. Der Scheiss passt nicht in eine Liste, also müssen es zwei sein. Und bei zwei Listen spielt deren Füllgrad keine Rolle. Exakt so waren deine Anforderungen, weitere gab es in deinem Eröffnungsposting nicht. Es wird immer deutlicher: Du bist einfach so dermassen krass unfähig, dass du nicht einmal die Anforderungen an den gesuchten Algorithmus formal korrekt darzustellen vermagst! Kein Wunder, dass du dann auch keinen implementieren kannst, der den (tatsächlichen) Anforderungen entspricht...
Diese zwei Anforderungen widersprechen sich meiner Ansicht nach: Torsten R. schrieb: > die Summe der Längen aller Listen-Elemente darf die feste Maximal-Länge > einer Liste nicht überschreiten. > Sind eh zwei Listen nötig, spielt der Füllgrad der Listen keine Rolle. Entweder gibt es allgemein eine maximale Länge für eine Liste (was die 1. Anforderung auszusagen scheint), oder eben nicht. Wenn es nur für manche Fälle ein Maximum geben soll, dann muss man dies in den Anforderungen klar darstellen.
:
Bearbeitet durch User
c-hater schrieb: > Es wird immer deutlicher: Du bist einfach so dermassen krass unfähig, > dass du nicht einmal die Anforderungen an den gesuchten Algorithmus > formal korrekt darzustellen vermagst! Ganz schön große Töne für jemanden, der leider am lesen der Anforderungen gescheitert ist. c-hater schrieb: > Wieso sollte das nicht optimal sein? Jedenfalls im Sinne des von dir > selber geposten Anforderungswerks. Der Scheiss passt nicht in eine > Liste, also müssen es zwei sein. Man braucht bei deinem Algorithmus aber nicht zwei, sondern drei Listen für die Werte aus dem Beispiel, und das widerspricht dieser Anforderung: Torsten R. schrieb: > Der Algorithmus soll eine bestimmte Menge von Elementen auf ein oder > zwei Listen aufteilen. Mark B. schrieb: > Diese zwei Anforderungen widersprechen sich meiner Ansicht nach: > > Torsten R. schrieb: >> die Summe der Längen aller Listen-Elemente darf die feste Maximal-Länge >> einer Liste nicht überschreiten. > >> Sind eh zwei Listen nötig, spielt der Füllgrad der Listen keine Rolle. > > Entweder gibt es allgemein eine maximale Länge für eine Liste (was die > 1. Anforderung auszusagen scheint), oder eben nicht. Die maximale Länge gibt es doch immer. Füllgrad ist nicht gleich maximaler Länge. Der Füllgrad gibt lediglich an, wieviel von der maximalen Länge tasächlich genutzt wurde. Es muss also nicht die eine Liste ganz voll gemacht werden und die andere möglichst wenig enthalten, sondern es kann sich z.B. auch gleichmäßig auf beide Listen verteilen. > Wenn es nur für manche Fälle ein Maximum geben soll, dann muss man > dies in den Anforderungen klar darstellen. Ich kann nicht erkennen, warum das der Fall sein sollte. Viel eher sehe ich hier einen Widerspruch: Torsten R. schrieb: > Hallo, > ich suche einen Algorithmus mit möglichst günstiger Laufzeit. Der > Algorithmus soll in meta template programming implementiert werden, von > daher wäre ein möglichst einfacher Algorithmus schön. Der einfachste Algorithmus ist meistens nicht gleichzeitig auch der schnellste. Man muss also eins von beiden priorisieren.
c-hater schrieb: > fülle eine Liste, bis nächstes Element nicht mehr reinpasst > fülle Rest in zweite Liste > > Das ist so trivial, da rollen sich einem bei dem Gedanken, dass für > dieses Problem irgendwer, der sich für einen Programmierer hält, die > Lösung erfragen muss, doch gelinde die Zehennägel hoch... Das liegt einfach daran, dass du weder das Problem noch deine angebliche Lösung auch nur annähernd verstanden hast. Dass du dich für einen Programmierer hältst beleidigt die ganze Zunft, daran ändern auch die von dir wie üblich ausgeteilten Beleidigungen nichts. Eine Schande nicht nur für das Forum. Georg
Hi Kai, Kai S. schrieb: > Das ganze ist unter dem Namen "Bin Packing" oder Behaelterproblem > bekannt. > (einziger Unterschied: die Anzahl der Behaelter ist konstant, bei Dir > nicht) ich hatte schon ein zwei Google-Versuche, aber wenn man nicht weiß wie der Rest der Welt das Problem nennt, kommt man natürlich nicht so schnell auf die Lösung der Anderen ;-) Danke schön! mfg Torsten
Hi Yalu, Yalu X. schrieb: > Sind die Elemente ganzzahlig und positiv? Jep! > Wenn ja, liefert der folgende Algorithmus eine optimale Teilmenge zur > Befüllung der ersten Ergebnisliste: Ok, ich versuche das gerade mal zu verstehen... :-) > lastelement[0] = -1; > for(int i=1; i<argc; i++) { > int el = atoi(argv[i]); > for(int len=MAXLEN; len>=0; len--) { > if(lastelement[len]) { Hier kann ich Dir nicht mehr folgen: lastelement[len] wäre doch lastelement[32] und das wäre meiner Meinung nach undefiniert oder 0. Wo ist mein Fehler? mfg Torsten
c-hater schrieb: > Es wird immer deutlicher: Du bist einfach so dermassen krass unfähig, > dass du nicht einmal die Anforderungen an den gesuchten Algorithmus > formal korrekt darzustellen vermagst! Muss man eine bedauernswerte Kreatur, wie dich, korrekterweise Soziopath nennen? https://de.wikipedia.org/wiki/Soziopathie
Yalu X. schrieb: > Draco schrieb: >> Und die Aufteilung auf die anderen Container? ;-) > > Das habe ich jetzt nicht ausprogrammiert, das Prinzip ist aber einfach: > > Nach dem erste Durchlauf entfernt man die bereits genutzten Elemente aus > der Menge und startet den Algorithmus mit der Restmenge erneut. Ja, da es nur 2 Listen gibt, wäre es tatsächlich relativ einfach. Wenn man die erste Liste optimal packt, muss der Rest einfach in die zweite Liste -> fertig ;-) Mir sind gerade noch zwei Besonderheiten eingefallen. Für den Fall, dass es Vorteilhaft wäre, die Elemente zuerst zu sortieren, dann würde eigentlich immer gelten: - Das größte Element muss in die erste Liste, wenn das nicht passt, gibt es auch keine Lösung. - Wenn das nächst kleinere Element nicht in die erste Liste past, muss es in die zweite Liste. - Erst wenn ein zweites Element in die erste Liste passt, muss bei der Suche hier verzweigt werden. Allerdings müsste man dann vorher sortieren.
Rolf M. schrieb: > Viel eher sehe ich hier einen Widerspruch: > > Torsten R. schrieb: >> Hallo, >> ich suche einen Algorithmus mit möglichst günstiger Laufzeit. Der >> Algorithmus soll in meta template programming implementiert werden, von >> daher wäre ein möglichst einfacher Algorithmus schön. > > Der einfachste Algorithmus ist meistens nicht gleichzeitig auch der > schnellste. Man muss also eins von beiden priorisieren. erwischt! ;-)
Torsten R. schrieb: > Hier kann ich Dir nicht mehr folgen: lastelement[len] wäre doch > lastelement[32] und das wäre meiner Meinung nach undefiniert oder 0. Wo > ist mein Fehler? Das Array ist so deklariert:
1 | static int lastelement[MAXLEN+1]; |
Von daher existiert lastelement[32] also.
Torsten R. schrieb: > Ok, ich versuche das gerade mal zu verstehen... :-) Zum besseren Verständnis noch ein paar Worte zur Bedeutung des Inhalts von lastelement[]: lastelement[len] = el (el > 0, 0 ≤ len ≤ MAXLEN) sagt aus, dass bereits eine Teilmenge gefunden wurde, deren Summe gleich len ist und dass das letzte dieser Elemente el ist. Ist hingegen lastelement[len] = 0 wurde noch keine solche Teilmenge gefunden. Zu Beginn sind alle Elemente von lastelement[] mit 0 intialisiert, nur lastelement[0] hat den Wert -1, was aussagt, dass bereits eine Teilmenge gefunden worden ist, deren Summe 0 ist. Diese Teilmenge ist trivialerweise die leere Menge. Da die leere Menge kein (letztes) Element hat, wird hier einfach ein beliebiger von 0 verschiedener Wert (-1) eingetragen. Im ersten Teil des Algorithmus werden nun für jedes Element der vorgegebenen Menge die Einträge von lastelement[] aktualisiert, so dass man daraus am Schluss ablesen kann, welche Summen von 0 bis MAXLEN überhaupt erreichbar sind. Im zweiten Teil wird dann zunächst die größtmögliche Summe gesucht (erste While-Schleife). Danach werden – ausgehend von dieser Summe – nacheinander die zur entsprechenden Teilmenge gehörenden Elemente ermittelt (zweite While-Schleife). Man kann den Algorithmus übrigens noch etwas optimieren, indem man im ersten Teil eine zusätzliche Abbruchbedingung einbaut, die anspricht, sobald eine Teilmenge gefunden worden ist, deren Summe exakt MAXLEN ist. In diesem Fall braucht nicht weitergesucht zu werden, und man kann direkt zur Ausgabe der Ergebnisse übergehen:
1 | lastelement[0] = -1; |
2 | for(int i=1; i<argc; i++) { |
3 | int el = atoi(argv[i]); |
4 | for(int len=MAXLEN; len>=0; len--) { |
5 | if(lastelement[len]) { |
6 | int sum = len + el; |
7 | if(sum<=MAXLEN && lastelement[sum]==0) { |
8 | lastelement[sum] = el; |
9 | if(sum == MAXLEN) |
10 | goto perfect_solution_found; |
11 | }
|
12 | }
|
13 | }
|
14 | }
|
15 | |
16 | perfect_solution_found: |
17 | ;
|
(Militante Goto-Gegner mögen mir die entsprechende Codezeile verzeihen ;-))
Hach ja dynamische Programmierung ist schon was feines :) trifft man im beruflichen Alltag leider nicht mehr so häufig an. Ich erinnere mich noch gerne an unser Schokoladengeplänkel Yalu ;)
D. I. schrieb: > Hach ja dynamische Programmierung ist schon was feines :) Ja, das gibt jedesmal einen kleinen Aha-Effekt, weil man damit oft Probleme sehr effizient lösen kann, die auf den ersten Blick nur in exponentieller Zeit lösbar sind. Trotzdem habe ich nie ganz verstanden, warum das Ganze "Dynamische Programmierung" heißt. > Ich erinnere mich noch gerne an unser Schokoladengeplänkel Yalu ;) Daran erinnerst du dich noch (ist ja schon über drei Jahre her)? Ich musste gerade nachschauen, worum es da überhaupt ging :) BTW: Es gibt da seit einiger Zeit einen neuen, schwer zu schlagenden ersten Platz mit gerade mal 0,000 s (also besser als 1 ms oder sogar besser als 0,5 ms, je nach Rundungsverfahren): https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=problem_stats&problemid=3540&category= Das warst doch nicht etwa du?
Yalu X. schrieb: > Trotzdem habe ich nie ganz verstanden, warum das Ganze "Dynamische > Programmierung" heißt. Das weiß ich auch nicht wie es zu dieser Begrifflichkeit kam. Yalu X. schrieb: > Daran erinnerst du dich noch (ist ja schon über drei Jahre her)? Ich > musste gerade nachschauen, worum es da überhaupt ging :) Ja die wenigen interessanten Diskussionen sind noch im Hinterstübchen verankert (wie z.B. auch das Backtracking-Bewässerungsproblem). Aber das Schokoladenproblem hatte ich erst vor kurzem wo anders verarbeitet, daher kam mir das wieder in den Sinn :) Yalu X. schrieb: > Das warst doch nicht etwa du? Nein, ich habe schon längere Zeit nichts mehr eingereicht. Meine Zeit ist im Moment eher begrenzt und ich verwende sie im Moment u.a. auf Dinge die ein paar € nebenbei versprechen :)
Yalu X. schrieb: > Trotzdem habe ich nie ganz verstanden, warum das Ganze "Dynamische > Programmierung" heißt. Weil Richard Bellman es so genannt hat: https://de.wikipedia.org/wiki/Dynamische_Programmierung
Yalu X. schrieb: > BTW: Es gibt da seit einiger Zeit einen neuen, schwer zu schlagenden > ersten Platz mit gerade mal 0,000 s (also besser als 1 ms oder sogar > besser als 0,5 ms, je nach Rundungsverfahren): > > https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=problem_stats&problemid=3540&category= Die Quelltexte der Lösungen kann man nicht sehen?
SearchMe schrieb: > Die Quelltexte der Lösungen kann man nicht sehen? Nein, es gibt halt vereinzelt auch retarded Abgaben die einfach nur die Lösungen ausgeben. Sowas ist möglich wenn man das input/output set findet im Netz. Solche Abgaben werden zwar nach einer Zeit wieder entfernt, aber das kann dauern. Aber in diesem Fall scheint die Zahl legit zu sein, dieser sgtlaugh scheint sehr ambitioniert zu sein.
D. I. schrieb: > SearchMe schrieb: >> Die Quelltexte der Lösungen kann man nicht sehen? > > Nein Schade. Den Unterschied zwischen Platz 2 (86 ms) und Platz 1 (0 ms/1 ms) hätte ich gern gesehen.
SearchMe schrieb: > Schade. Den Unterschied zwischen Platz 2 (86 ms) und Platz 1 (0 ms/1 ms) > hätte ich gern gesehen. Meine Vermutung ist, dass ggü. Yalu er eine bessere Methode hat die Teilmengen zu berechnen. (Vermutlich einmalig precomputed) Das wäre mein erster Verdacht.
Yalu X. schrieb: > Zum besseren Verständnis noch ein paar Worte zur Bedeutung des Inhalts > von lastelement[]: > > lastelement[len] = el (el > 0, 0 ≤ len ≤ MAXLEN) > > sagt aus, dass bereits eine Teilmenge gefunden wurde, deren Summe gleich > len ist und dass das letzte dieser Elemente el ist. Ist hingegen > > lastelement[len] = 0 > > wurde noch keine solche Teilmenge gefunden. > > Zu Beginn sind alle Elemente von lastelement[] mit 0 intialisiert, nur > lastelement[0] hat den Wert -1, was aussagt, dass bereits eine Teilmenge > gefunden worden ist, deren Summe 0 ist. Diese Teilmenge ist > trivialerweise die leere Menge. Da die leere Menge kein (letztes) > Element hat, wird hier einfach ein beliebiger von 0 verschiedener Wert > (-1) eingetragen. Ok, den Teil hatte ich am Anfang übersehen, ich hatte nur dass innere `if` gesehen und mich gefragt: "Wann soll das den ausgeführt werden?" ;-) Jetzt ist es mir aber klar. Sehr pfiffig! ;-) Die innere Schleife könnte man noch auf "for(int len=MAXLEN-el; len>=0; len--)" verkürzen. Schönen Dank an Alle! Jetzt muss ich mal gucken, was sich davon am besten umsetzen lässt. mfg Torsten
Torsten R. schrieb: > Die innere Schleife könnte man noch auf "for(int len=MAXLEN-el; len>=0; > len--)" verkürzen. Stimmt, das würde noch einmal ein paar Schleifendurchläufe einsparen.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.