1586139 Besucher [171 Heute]
Ehrliche Teilung

von Dennis Theurer

  • Informatik-Arbeit (12. Klasse)
  • 15 Punkte

Aufgabe

 

Ehrliche Teilung

Eine Schar Kinder hat Gegenstände (ausgemusterte Spielsachen) auf dem Flohmarkt verkauft. Nach dem Ende des Marktes sind einige Gegenstände übriggeblieben; sie sollen auf die Kinder ehrlich verteilt werden. Das heißt: der Wert der Gegenstände, die jedes Kind bekommt, sei für alle gleich. Was auf diese Weise nicht verteilt werden kann, bleibt auf dem Markt zurück - und dessen Wert soll natürlich so gering wie möglich sein. Kinder und Gegenstände sind jeweils durchnumeriert.

Auftrag: Schreibe ein Programm, das die „ehrliche Teilung" vornimmt. Das heißt: die Summe der Werte der zurückgelassenen Gegenstände soll so klein wie möglich sein, und die Summe der Werte der Artikel, die jedes Kind bekommt, muss für alle Kinder gleich sein.

Eingabe: In der ersten Zeile steht die Anzahl k der Kinder (1 < k < 10). In der zweiten Zeile steht die Anzahl s der zu verteilenden Gegenstände (3 < s < 100). In der dritten Zeile stehen die s Werte w der Gegenstände (in Cent), wobei 0 < w < 1000 gilt.

Ausgabe: Genau s Zahlen, die angeben, wer den ersten, zweiten, ... Gegenstand bekommt; eine 0 an Stelle i bedeutet, dass der Gegenstand Nr. i zurückgelassen wird.

Beispiel: Eingabe

3

 

 

 

 

 

 

7

 

 

 

 

 

 

78

300

12

222

140

145

15

Das heißt: Es handelt sich um k = 3 Kinder und s = 7 Gegenstände mit den Werten 78 Cent, 300 Cent usw. Kind 1 bekommt die Gegenstände 1 und 4 (Wert: 78 + 222 = 300), Kind 2 bekommt Gegenstand 2 (Wert: 300), Kind 3 bekommt die Gegenstände 5, 6, 7 (Wert: 140 + 145 + 15 = 300).

 

 

1. Ziel der Arbeit

Das Ziel der Arbeit ist es, die Aufgabe Ehrliche Teilung zu lösen.

2. Problemanalyse und Lösungsidee

Bei der Aufgabe müssen Gegenstände mit einem gegebenen Wert auf eine bestimmte Anzahl an Kindern verteilt werden. Dabei gelten die Bedingungen, dass der Gesamtwert der erhaltenen Gegenstände pro Kind genau gleich ist. Um dies zu erreichen, können auch Gegenstände nicht verteilt werden, aber ihr Wert sollte so gering wie möglich sein.

Als Lösungsverfahren wird das Rückziehungsverfahren verwendet, da es so möglich ist, alle Kombinationen an Verteilungen der Gegenstände durchzugehen, um so die beste Teilung zu ermitteln. Außerdem bietet dieses Verfahren an, Abbruchkriterien zu verwenden, die die Berechnung wesentlich beschleunigen (siehe Kapitel 5).

Jedem Kind wird einmal der erste Gegenstand zugewiesen und es wird der Gesamtwert an Gegenständen, die dieses Kind nun besitzt, gespeichert. Allerdings wird dieser Gegenstand auch einmal niemandem zugewiesen, um so die Möglichkeit zu schaffen, ihn nicht aufzuteilen.

Dieser Vorgang wird mit jedem Gegenstand rekursiv wiederholt. Sind alle Gegenstände verteilt, wird kontrolliert, ob eine „ehrliche Teilung" vorliegt, also ob die Teilung den gestellten Bedingungen entspricht. Liegt dieser Fall vor, wird diese Teilung als die beste Teilung gemerkt, sofern es nicht eine bereits bessere Teilung gibt, also der Wert der zurückgelassenen Gegenstände niedriger ist. Wenn dieser Wert jedoch 0 ist, liegt eine unübertreffliche Teilung vor und der Algorithmus kann abgebrochen werden, da ja nur nach einer besten Lösung gefragt ist und es kein weiteres Kriterium gibt, durch das Teilungen mit einem Wert der zurückgelassenen Gegenstände von 0 besser gewertet wird als eine andere.

3. Programmentwicklung 

3.1 Aufbau des Programms

Das Programm ist in vier Funktionen unterteilt:

  • void main: Hauptfunktion, mit der das Programm aufgerufen wird (siehe 3.2).
  • void SucheLoesung: Funktion, die den Algorithmus enthält (siehe 3.3).
  • boolean IstEhrlicheTeilung: Gibt true zurück, wenn eine „ehrliche Teilung" vorliegt, sonst false.
  • void MerkeTeilung

Kopiert die Reihung mit der Aufteilung der Gegenstände, damit diese Lösung nicht vom Algorithmus wieder überschrieben wird.

3.2 Funktion: main 

Beim Start des Programms wird die Hauptfunktion main aufgerufen.

Diese liest die Benutzereingabe, verarbeitet die Eingaben und gibt schließlich die Lösung aus.

Nach der Eingabe der Anzahl der Kinder und der Anzahl der Gegenstände werden Reihungen für die Gegenstandswerte und ihre Besitzer initialisiert, sowie eine Reihung für die beste Lösung. Eine weitere Reihung gibt an, welches Kind was für einen Gesamtwert an Gegenständen besitzt. Dabei ist die Reihung um eins größer als die Anzahl der Kinder, da berücksichtigt werden muss, dass auch Gegenstände nicht verteilt werden können und deren Wert wird dann im 0. Glied der kinderAnteile Reihung gespeichert, sodass die Zählung für die Kinder bei 1 beginnt. Genauso werden Gegenstände, die dem „0. Kind" zugewiesen werden, als nicht verteilt gewertet.

Eine weitere Variable verlorenerWert gibt an, wie groß der Wert der zurückgelassenen Gegenstände der besten Lösung ist.

werte = new int[anzahlObjekte];

besitzer = new int[anzahlObjekte];

besteLoesung = new int[anzahlObjekte];

kinder = new int[anzahlKinder + 1];

loesungGefunden = false;

Anschließend werden die Gegenstandswerte in einer Zählschleife durch Eingaben ermittelt. Zusätzlich wird noch ein Mittelwert errechnet, den ein Kind an Gegenständen besitzen darf, der später im Algorithmus als Abbruchskriterium verwendet wird.

for (int i = 0; i < anzahlObjekte; i++) {

  System.out.print("Wert des "+(i+1)+". Gegenstandes: ");

werte[i] = Integer.parseInt(tastatur.readLine());

mittelwertProKind += werte[i];

} // Ende for

mittelwertProKind /= anzahlKinder;

Nun wird der Lösungsalgorithmus aufgerufen. Ihm wird 0 übergeben, was bedeutet, dass der 1. Gegenstand verteilt werden soll (Zählung beginnt bei 0).

SucheLoesung(0);

Schließlich wird kontrolliert, ob eine Lösung gefunden wurde, und diese dann ausgegeben.

System.out.println("Beste Loesung:");

if (verlorenerWert > -1) {

  for (int i = 0; i < besteLoesung.length; i++)

    System.out.print(besteLoesung[i] + " ");

  System.out.print(" ");

} // Ende if

else

  System.out.println("Keine Loesung gefunden.");

3.3 Funktion: SucheLoesung 

Diese Funktion sucht rekursiv eine Lösung für die ehrliche Teilung mit den zuvor ermittelten Daten. Ihr wird die Nummer des aktuellen Gegenstandes übergeben (Zählung beginnt bei 0). Ist der letzte Gegenstand erreicht, wird kontrolliert, ob es sich um eine „ehrliche Teilung" handelt, und gegebenenfalls wird die aktuelle Teilung als Lösung gespeichert.

if(nr == anzahlObjekte) {

  if (IstEhrlicheTeilung())

    MerkeTeilung();

} // Ende if

Handelt es sich nicht um eine „ehrliche Teilung" oder ist der letzte Gegenstand noch nicht erreicht, muss erneut kontrolliert werden, ob der aktuelle Gegenstand die Reihung der Gegenstände überschreitet. Außerdem bricht der Algorithmus ab, wenn eine Lösung gefunden wurde und die Variable verlorenerWert 0 ist, also keine bessere Lösung mehr gefunden werden kann.

else {

  if (loesungGefunden && verlorenerWert == 0)

    return;

Nun wird jedem Kind und einmal niemandem der aktuelle Gegenstand zugewiesen und der Wert in der Reihung für den Gesamtwert der Gegenstände, die ein Kind hat, wird um den Wert des aktuellen Gegenstandes erhöht. Wenn es bereits eine Lösung gibt, wird die Funktion nur dann rekursiv erneut aufgerufen, wenn der Wert der zurückgelassenen Gegenstände kleiner als bei der bereits gefundenen Lösung ist. Außerdem darf das Kind keinen größeren Wert besitzen als der Quotient aus Gesamtwert und Anzahl der Kinder, da sonst keine „ehrliche Teilung" mehr möglich wäre, weil die Kinder nicht alle den gleichen Wert erhalten könnten. Die Funktion ruft sich selbst auf und erhöht dabei den aktuellen Gegenstand um 1. Anschließend muss der Wert der Gegenstände, die das Kind, dem der Gegenstand zugewiesen wurde, wieder um den Wert des aktuellen Gegenstandes verkleinert werden, damit man den Gegenstand einem anderen Kind zuteilen kann.

for (int i = 0; i <= anzahlKinder; i++) {

  besitzer[nr] = i;

  kinderAnteile[i] += werte[nr];

  if ((!loesungGefunden || kinderAnteile[0] < verlorenerWert)

    && (i == 0 || kinderAnteile[i] <= mittelwertProKind))

    SucheLoesung(nr + 1);

  kinderAnteile[i] -= werte[nr];

} // Ende for

4. Benutzerdialog 

>java Teilung

Anzahl der Kinder: 3

Anzahl der Gegenstaende: 7

Wert des 1. Gegenstandes: 78

Wert des 2. Gegenstandes: 300

Wert des 3. Gegenstandes: 12

Wert des 4. Gegenstandes: 222

Wert des 5. Gegenstandes: 140

Wert des 6. Gegenstandes: 145

Wert des 7. Gegenstandes: 15

Beste Loesung:

1 2 0 1 3 3 3

5. Diskussion

Die Zeit, die das Programm braucht, steigt exponentiell zur Anzahl der Gegenstände und erhöht sich weiterhin mit der Anzahl der Kinder.

In das Programm wurden einige Abbruchbedingungen eingebaut.

Der Algorithmus bricht ab, wenn ...

  • ... es bereits eine Lösung gibt, die von keiner überboten werden kann (Wert der zurückgelassenen Gegenstände ist 0)
  • ... es bereits eine Lösung gibt und der Wert der zurückgelassenen Gegenstände bereits größer ist als von der gefundenen Lösung.
  • ... ein Kind einen größeren Wert besitzt als der Quotient aus Gesamtwert aller Gegenstände und der Anzahl der Kinder.

Trotz dieser Bedingungen arbeitet der Algorithmus nur sehr langsam bei steigenden Gegenständen und Kindern.

Dennoch steigern sie die Effizienz des  Algorithmus erheblich.

Die Abbildung rechts zeigt das Prinzip des Mittelwertskriteriums. Es werden 4 Gegenstände mit jeweils gleichem Wert an 3 Kinder verteilt. Natürlich kann es keine „ehrliche Teilung" mehr geben, wenn eines der Kinder zwei Gegenstände erhält. Der Algorithmus kann den Graphen also bereits nach Verteilen des ersten Gegenstandes erheblich kürzen.

Bei Werten von 4 Kindern und 13 Gegenständen brauchte der Algorithmus ohne die letzten beiden oben aufgezählten Bedingungen insgesamt 47 Sekunden. Nach Einbauen der Bedingungen sank die Zeit auf 3 Sekunden! Die Aufrufe der Funktion SucheLoesung sinken von 1.525.878.906 auf 35.055.849.

Gerade Bedingungen wie diese zeigen die Effizient des Rückziehungsverfahrens gegenüber Algorithmen die stur jede denkbare Lösung ermitteln, denn der Vorteil von Backtracking ist ja durch Abbruchbedingungen frühzeitig zu erkennen, dass der Weg zu keiner Lösung führt, wodurch sich die Anzahl der Aufrufe auf ein Bruchteil verkleinert.

Bei einer kleinen Menge an Gegenständen und Kindern fallen die Abbruchbedingungen allerdings nicht ins Gewicht.

 

6. Programmtext

import java.io.*;

public class Teilung {

  static int[] werte;

  static int[] besitzer;

  static int[] kinderAnteile;

  static int[] besteLoesung;

  static int verlorenerWert;

  static int mittelwertProKind;

  static int anzahlObjekte;

  static int anzahlKinder;

  static boolean loesungGefunden;

  static void SucheLoesung (int nr) {

    if(nr == anzahlObjekte) {

      if (IstEhrlicheTeilung())

        MerkeTeilung();

    } // Ende if

    else {

      if (loesungGefunden && verlorenerWert == 0)

        return;

      for (int i = 0; i <= anzahlKinder; i++) {

        besitzer[nr] = i;

        kinderAnteile[i] += werte[nr];

        if ((!loesungGefunden || kinderAnteile[0] < verlorenerWert)

          && (i == 0 || kinderAnteile[i] <= mittelwertProKind))

          SucheLoesung(nr + 1);

        kinderAnteile[i] -= werte[nr];

        } // Ende for

    } // Ende else

  } // Ende SucheLoesung

  static boolean IstEhrlicheTeilung () {

    // Kontrolliert, ob die Teilung "ehrlich" ist

    for (int i = 2; i <= anzahlKinder; i++)

      if (kinderAnteile[i] != kinderAnteile[i-1])

        return false;

    return true;

  } // Ende IstEhrlicheTeilung

  static void MerkeTeilung() {

    // Kopiert die aktuelle Teilung (besitzer) in besteLoesung

    for (int i = 0; i < anzahlObjekte; i++) {

      besteLoesung[i] = besitzer[i];

    }

    verlorenerWert = kinderAnteile[0];

    loesungGefunden = true;

  } // Ende MerkeTeilung

  public static void main (String[] args) throws IOException {

    BufferedReader tastatur =

      new BufferedReader(new InputStreamReader(System.in));

    System.out.print("Anzahl der Kinder: ");

    anzahlKinder = Integer.parseInt(tastatur.readLine());

    System.out.print("Anzahl der Gegenstaende: ");

    anzahlObjekte = Integer.parseInt(tastatur.readLine());

    werte = new int[anzahlObjekte];

    besitzer = new int[anzahlObjekte];

    besteLoesung = new int[anzahlObjekte];

    kinderAnteile = new int[anzahlKinder + 1];

    loesungGefunden = false;

 

    for (int i = 0; i < anzahlObjekte; i++) {

      System.out.print("Wert des "+(i+1)+". Gegenstandes: ");

      werte[i] = Integer.parseInt(tastatur.readLine());

      mittelwertProKind += werte[i];

    } // Ende for

    mittelwertProKind /= anzahlKinder;

    SucheLoesung(0);

    System.out.println("Beste Loesung:");

    if (verlorenerWert > -1) {

      for (int i = 0; i < besteLoesung.length; i++)

        System.out.print(besteLoesung[i] + " ");

      System.out.print(" ");

    } // Ende if

    else

      System.out.println("Keine Loesung gefunden.");

  } // Ende main

} // Ende Teilung

 

Kategorie: Informatik | Kommentare (2)