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 findenTorsten 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
intmain(intargc,char*argv[]){
7
staticintlastelement[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(inti=1;i<argc;i++){
14
intel=atoi(argv[i]);
15
for(intlen=MAXLEN;len>=0;len--){
16
if(lastelement[len]){
17
intsum=len+el;
18
if(sum<=MAXLEN&&lastelement[sum]==0)
19
lastelement[sum]=el;
20
}
21
}
22
}
23
24
// Ausgabe der gefundenen Elemente
25
26
intlen=MAXLEN;
27
while(lastelement[len]==0)
28
len--;
29
printf("Genutzte Gesamtlänge: %d von %d\n",len,MAXLEN);
30
while(len){
31
intel=lastelement[len];
32
printf("%d ",el);
33
len-=el;
34
}
35
printf("\n");
36
37
return0;
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:
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.
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:
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(inti=1;i<argc;i++){
3
intel=atoi(argv[i]);
4
for(intlen=MAXLEN;len>=0;len--){
5
if(lastelement[len]){
6
intsum=len+el;
7
if(sum<=MAXLEN&&lastelement[sum]==0){
8
lastelement[sum]=el;
9
if(sum==MAXLEN)
10
gotoperfect_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 :)
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.
Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.
Wichtige Regeln - erst lesen, dann posten!
Groß- und Kleinschreibung verwenden
Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang
Announcement: there is an English version of this forum on 
Thread beobachten
Seitenaufteilung abschalten