Gewichte Addieren

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

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?

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.

> 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.

kannst du die gewichtsliste mal hier als txt-datei reinstellen?