Hallo zusammen und guten Morgen.
Ich habe 1500 verschiedene Tüten von ~500g bis 1000g Es sollen immer 15
Tüten in ein Paket und alle Pakete sollen möglichst gleich schwer
werden.
Ich habe alle Gewichte in eine Exel Tabelle gehackt und durch 100
geteilt. somit weiß ich jetzt das jedes Paket 10230g wiegen sollte.
Aber jetzt komme ich nicht mehr so recht weiter. Ich könnte jetzt die
Gewichte aus der Liste suchen welche zusammen am besten das Ergebnis
darstellen aber ich denke da gibt es Formeln oder Möglichkeiten die das
viel besser können?
Könnt ihr mir da mal verraten wie sich so etwas nennt oder wonach ich
suchen muss?
Das ist das sogenannte Rucksack-Problem. Dieses ist nur mit gigantischem
Rechenaufwand zu lösen (Exponentielle Laufzeit, also bei dir N^1500 -
die Sonne explodiert vorher). Da es bei dir vermutlich nicht auf das
Gramm ankommt, kannst du ja mal nach approximativen Lösungen des
Rucksack-Problems suchen.
Wenn immer 15 Tüten in ein Paket sollen, ist das wegen der hohen Zahl
der Kombinationen rechenintensiv. Erster Ansatz wäre eine Bildung von
32-er-Gruppen und Suche innerhalb dieser Auswahl.
Wie schaut die statistische Verteilung der Gewichte aus?
Wie genau soll es sein?
Nenne die ersten beiden Ziffern Deiner PLZ.
Deutlich entspannt sich die Sache, wenn du einen akzeptablen
Toleranzbereich angeben kannst. Je grösser, desto einfacher die
Sortiererei.
Anschliessend kann man noch versuchen, aus dem jeweils schwersten und
leichtesten zu tauschen und damit die tatsächliche Toleranz weiter zu
verkleinern.
1. Auf die 1500 Tüten zufällig zugreifen und diese zu 100 Paketen je 15
zusammenstellen.
Wie gut ist das Ergebnis?
2. Tüten die zu schwer bzw. zu leicht sind untereinander ausgleichen.
Wie gut ist das Ergebnis?
Lässt sich das Ergebnis durch Wiederholung von 2. verbessern?
Rucksack-Problem. Klingt komisch aber das trift es wohl.
Genauigkeit naja auf 10g wird es nicht ankommen. Immerhin weiß ich jetzt
wonach ich suchen kann :)
> Sind in den Tüten Mikrocontroller drin
Ich vermute mal, daß er diese Aufgabe durch einen Algorithmus auf einem
Mikrocontroller lösen soll. Typsich Schule.
Im echten Leben würde man das wohl kaum so realisieren. Da würde in
PC/Server vorgeben, was die Maschine wo hin stecken soll. Der µC in der
Maschine würde nur die Kommandos ausführen.
Stefan U. schrieb:> Ich vermute mal, daß er diese Aufgabe durch einen Algorithmus auf einem> Mikrocontroller lösen soll. Typsich Schule.
Klar, weil der Informatik-Lehrer keine Ahnung von Komplexität hat und
die Schüler NP-vollständige Probleme lösen lässt.
Stefan U. schrieb:> Da würde in> PC/Server vorgeben, was die Maschine wo hin stecken soll. Der µC in der> Maschine würde nur die Kommandos ausführen.
Empfangen die Mikrocontroller in der Motorsteuerung deines Autos ihre
Befehle auch von einem Server oder rechnen die doch selber?
Hi
Dr. Sommer schrieb:> Empfangen die Mikrocontroller in der Motorsteuerung deines Autos ihre> Befehle auch von einem Server oder rechnen die doch selber?
Ja
Bei Oder-Fragen immer so eine Sache :)
Zum Problem:
Früher hatte ich Mal für ein Modelleisenbahnplanprogramm (hehe, was ein
Wort) eine Routine geschrieben, Die aus allen vorhandenen
Gleislängen(Winkeln, Radien, ... hier die Einzelgewichte) mir die besten
Kombinationen zur gesuchten Länge (ect.) zusammen rechnete, wobei hier
dann noch danach unterschieden wurde, mit wie viel 'Spiel' ich bei
welchem Preisunterschied leben könnte.
Unterm Strich habe ich 'nur' das möglichst längste Gleis 'eingepackt',
solange Das halt geht.
Am Schluß bleibt eine Differenz (+/-) zum Soll.
Bei Dir ist ja die Anzahl der Einzelgewichte begrenzt, musst also drauf
achten, daß Du nicht 'unendlich viele leichte Tüten' in einen Karton
rein sortierst.
Wie ich nach der 1.ten Lösung weiter gegangen bin - kA - hab damals aber
auch den einen oder anderen Tag darin versenkt - das Programm kam dann
auf Datasette, könnte also schon was her sein :)
MfG
Geneva [...] ist eine [...] Programmbibliothek, die miteinander kombinierbare Algorithmen zur näherungsweisen, Computer-gestützten Lösung von Optimierungsproblemen bereitstellt.
Es ergibt dann also 100 (!) Pakete a 15 Tüten.
Was kommt denn heraus, wenn man es so macht:
1) In Paket 1 die leichteste und schwerste Tüte.
2) In Paket 2 die leichteste (verbliebene) und
schwerste (verbliebene) Tüte.
usw. usw.
100) In Paket 100 die leichteste und schwerste ..., wie vor.
101) In Paket 100 die leichteste und schwerste ..., wie vor.
usw. usw.
200) In Paket 1 die leichteste und schwerste ...
201) In Paket 1 die leichteste und schwerste ...
202) In Paket 2 die leichteste und schwerste ...
usw. usw.
1401) In das leichteste von den 100 Paketen die schwerste
von den verbliebenen Tüten, dieses Paket ist fertig.
1402) In das leichteste von den jetzt 99 Paketen die schwerste
von den verbliebenen Tüten, dieses Paket ist fertig.
usw. usw.
1500) Die letzte Tüte ins letzte Paket, fertig.
Zuerst mal ist die Optimierungsfunktion nicht bekannt. Was soll "alle
Pakete ... möglichst gleich schwer" denn genau bedeuten und was soll das
Optimum sein, wenn es keine Lösung mit 100 genau gleich schweren Paketen
gibt?
Da es andererseits keine vom Gewicht unabhängige Nutzenfunktion gibt,
ist das auch nicht das Rucksackproblem. WIMRE ist dieses vereinfachte
Problem mit einem Greedy-Algorithmus zu lösen.
Man würde sich einfach ein Minimal- und ein Maximalgewicht vorgeben und
dann beginnend mit dem schwersten Päckchen seine Tüte packen. Immer wenn
man das Maximum überschreitet, tut man das Päckchen zurück und versucht
das nächstleichtere. Naja. Ein Greedy-Algorithmus halt.
> Was soll "alle Pakete ... möglichst gleich schwer" denn genau bedeuten
Ich schätze, der Lehrer möchte sehen, wie lange es dauert, bis der erste
Schüler genau diese Frage stellt. Oder er will sehen, ob alle Schüler
übers Wochenende darauf gekommen sind, danach zu fragen.
