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.
Versuch: Zuerst die 15 schwersten absteigend eintüten, dann die nächsten 15 in umgekehrter Reihenfolge, usw.. Ob's klappt? Waldo
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, oder was hat das Problem mit dem Themenbereich dieses Unterforums zu tun?
Hallo, Erweiterung: Immer das Schwerste der Schwersten 15 in die leichteste der 15 Tüten mit n-1 Elemente. Waldo
> 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
Kuddel schrieb: > 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? Klingt nach einem guten Einsatzzweck fuer einen genetischen Algorithmus :) https://de.wikiversity.org/wiki/Kurs:Genetische_Algorithmen Geneva Optimierungsumgebung https://de.wikipedia.org/wiki/Geneva_Optimierungsumgebung
1 | 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.
Rudi A. schrieb: > kannst du die gewichtsliste mal hier als txt-datei reinstellen? Warum? Willst du seine Hausaufgabe für ihn machen?
Thread beobachten
Seitenaufteilung abschaltenBitte 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.