Katrin Käfer möchte ein großes Fest feiern. Dafür sind etliche
Aufgaben zu erledigen: Salate machen, Pizza vorbereiten, Zimmer
ausräumen, Nachbarn warnen und dergleichen mehr. Katrin möchte
nicht die ganze Arbeit alleine machen und überlegt sich daher,
einige ihrer Freundinnen und Freunde zur Mitarbeit heranzuziehen.
Nun stellt sich natürlich die Frage, wie viele Personen sie um
Mithilfe bitten soll. Etwas formaler stellt sich ihr Problem wie folgt dar: Es sind n Aufgaben zu erledigen. Die einzelnen Aufgaben sind nicht mehr teilbar. Für die i-te Aufgabe ist die Zeit ti zu veranschlagen. Katrin allein würde also die Zeit t1 + t2 + ... + tn benötigen. Jede Person, die Katrin helfen könnte, kann nur einen Nachmittag, d.h. nicht mehr als 5 Stunden Zeit aufbringen. Um die minimale Anzahl Helfer zu berechnen, müßte Katrin alle Möglichkeiten, Kombinationen von Aufgaben auf Helfer zu verteilen, ausprobieren. Bei den vielen zu erledigenden Aufgaben dauert ihr das aber zu lange. Aufgabe: Entwirf eine Strategie, die folgendes leistet: - Sie ermittelt nicht die optimale Lösung durch Probieren aller Kombinationen. - Sie ordnet nicht einfach jeder Person genau eine Aufgabe zu. - Sie verplant höchstens doppelt so viele Personen, wie im besten Fall nötig gewesen wären. Beschreibe Deine Strategie und beweise, daß Katrin damit nicht mehr als doppelt so viele Helfer einspannt, wie nötig gewesen wären. Schreibe ein Programm, das Deine Strategie realisiert. Gib für n = 9, t1 = t2 =...= t7 = 45 min, t8 = 165 min, t9 = 105 min und pro Person zur Verfügung stehender Zeit 300 min an, zu welchem Ergebnis Deine Strategie führt (nicht die von Hand errechnete optimale Lösung!). Wende Deine Strategie außerdem auf 10.000 mit dem Zufallszahlengenerator erzeugte Zahlen im Bereich 1 bis 20 und pro Person zur Verfügung stehender Zeit 25 an (n = 10.000, ti Element aus {1,..., 20}) und gib an, wieviele Personen benötigt werden und wie lange sie im Durchschnitt arbeiten. |
|
![]() zurück weiter Index |