Einfach nur, damit der Thread dann ein Ende hat: Zwei doch einfache Ansätze:
1. Ansatz:
a. Wir holen uns das größte und das kleinste Stück.
b. ist eines der beiden Stücke nicht mehr zu verändern? -> wir sind fertig.
c) Wir ermitteln die Abweichung bei beiden Stücken. Die kleinere Abweichung wird dem größeren Stück weggenommen und dem kleinsten Stück gegeben.
d) Es geht bei a) weiter
2. Ansatz (ähnlich):
Wir filtern:
- die größten Stücke in eine Liste
- die kleinsten Stücke in eine Liste
==> So lange in beiden Listen Elemente sind, nehmen wir jeweils das erste Element, ermitteln die Abweichung, nehmen die kleinere Abweichung um diese dem größeren Element wegzunehmen und dem kleineren Element zu geben. Anschließend prüfen wir beide Elemente. Mindestens eins erfüllt das Kriterium nicht mehr und wird aus der jeweiligen Liste entfernt.
Generell ist anzumerken: Es ist möglich, dass wir Elemente haben, die nicht ausgeglichen werden.
Beispiel: 3 mal 0.4% zu wenig, der 4te hat 1.2% zu viel. Da die ersten 3 Stücke aber nicht ausgeglichen werden sollen ist es nicht möglich, das 4te Element auszugleichen. (Ich hatte es so verstanden, das Stücke mit < 0.5% Abweichung nicht verändert werden sollen. )
Sollte die Aufgabe es aber anders meinen, so dass die Stücke nicht verändert werden müssen es aber durchaus erlaubt ist: Dann sind die Algorithmen zu verändern.
Bei 1.: Wir ändern nur die Abbruchbedingung: Erst wenn kein Element mehr anzupassen ist, brechen wir ab.
Bei dem 2. Ansatz ist es nicht ganz so trivial. Da muss die Liste, die noch Elemente hat, halt weiter bearbeitet werden. Dazu könnte man statt zwei Listen eben 4 Listen führen. größere Elemente außerhalb / innerhalb der Toleranz und das auch mit kleineren Elementen. Sobald eine Liste leer ist, wird dort mit der Liste innerhalb der Toleranz weiter gemacht bis auch die zweite Liste erledigt ist.
Und weil es so schön ist, einfach noch einen 3. Ansatz:
Ich sortiere die Liste nach Größe.
Dann summiere ich die Abweichung bei den zu veränderten Elementen:
Dann habe ich ein Delta zu Gross und ein Delta zu klein. Das größere Delta wird genommen und alle Elemente werden direkt auf 25 gesetzt.
Das andere Delta wird genommen als Vorrat und ich gehe die Liste von der anderen Seite durch:
- Für jedes Element schaue ich mir das Delta zur 25 an und vergleiche mit meinem Vorrat. Das kleinere Element wird genommen, der Vorrat reduziert und das Element ausgeglichen.
- Abbruch ist: Vorrat ist leer.
Und das alles hat nichts mit Programmieren zu tun. Dies hat einfach damit zu tun, dass man ein Problem hat und dieses irgendwie lösen muss.
Kuchenstücke ist doch anschaulich. Man kann aber auch Bonbons nehmen. Jeder soll 250 Bonbons haben. +/- 5 Bonbons ist ok.
Was macht man dann um das auszugleichen? Das ist - ganz nebenbei - ein Problem, das Kinder schon lösen können in der Grundschule.
