Ein gläubiger Mensch hatte in seinem Testament folgende Regelung für die Aufteilung seines Erbes getroffen, das aus einer Truhe mit alten Münzen bestand:
Jeder seiner beiden Söhne erhält genau die Hälfte des Gesamtwerts der Münzen, sofern das Erbe gleichmäßig aufgeteilt werden kann. Ist eine gerechte Aufteilung nicht möglich, dann soll das gesamte Erbe an ein Kloster fallen. Schreiben Sie eine MATLAB Funktion erbteilung(Muenzen), die alle möglichen Teilungen des Erbes auflistet. Der Wert der Münzen in der Truhe wird dazu über den Vektor Muenzen angegeben. Ist eine gerechte Teilung nicht möglich, wird der Text „Das Erbe fällt an das Kloster.“ ausgeben. Wenden Sie zur Bearbeitung des Problems das Entscheidungsbaumverfahren an. Definieren Sie in einem ersten Schritt die Entscheidungsstufen und die möglichen Alternativen für jede Entscheidung. Bestimmen Sie geeignete Kriterien, um eine mögliche Teillösung auf Zulässigkeit und Sinnhaftigkeit zu überprüfen und vermeiden Sie dadurch Lösungspfade, die aufgrund der Aufgabenstellung zu keiner Lösung mehr führen können!
Gehen Sie von folgenden Testdaten aus:
Anzahl der Münzen : 10
Werte der Münzen : 15, 27, 7, 23, 56, 13, 22, 5, 42, 34
Lösung:
Bruder 1: 27, 56, 5, 34
Bruder 2: 15, 7, 23, 13, 22, 42
oder:
Bruder 1: 15, 7, 23, 13, 22, 42
Bruder 2: 27, 56, 5, 34
Lösung
function erbteilung(Muenzen) N=length(Muenzen); % Anzahl der Münzen (Entscheidungsstufen) aktLoes=false(N,1); % aktuelle Auswahl % aktLoes(k)=True->k-te Münze geht an % Bruder 1 % aktLoes(k)=False -> k-te Münze geht an % Bruder 2 count=0; % Anzahl der gefundenen Lösungen aktS=0; % aktuelle Summe der Münzen von Bruder 1 Erbsumme=sum(Muenzen); % Gesamtes Erbe if ~mod(Erbsumme,2) % suche Lösung, falls Erbsumme gerade ok=entscheide(1); % beginne auf der ersten Stufe, % gehe dann rekursiv in die Tiefe else ok=0; end if ~ok disp('Das Erbe fällt an das Kloster') end function erg=entscheide(aktStufe) % Backtracking Funktion % erg ist 1, falls mindestens eine Lösung gefunden wurde erg=0; % Initialisierung: noch keine Lösung gefunden % Schleife über alle Alternativen auf der aktuellen Stufe for i=0:1 % weise Entscheidung probehalber zu aktLoes(aktStufe)=i; if i % erhöhe Erbe von Bruder 1 um aktuelle Münze aktS=aktS+Muenzen(aktStufe); end % überprüfe Entscheidung auf Zulässigkeit und % Sinnhaftigkeit if aktS<=Erbsumme/2 && aktS+sum(Muenzen(aktStufe+1:end))>=Erbsumme/2 if aktS==Erbsumme/2 % korrekte Lösung gefunden? count=count+1; % Zähler inkrementieren % aktuelle Lösung ausgeben disp(['Die ' num2str(count) '. Lösung lautet:']) disp('Bruder 1:') disp(Muenzen(aktLoes)) disp('Bruder 2:') disp(Muenzen(~aktLoes)) erg=1; %return % Abbruch nach 1. Lösung else if aktStufe<N % noch weitere Münzen vorhanden? % fahre mit nächster Münze fort erg=entscheide(aktStufe+1); %if erg % Abbruch nach 1. Lösung % return %end end end end % nehme Entscheidung wieder zurück aktLoes(aktStufe)=0; if i aktS=aktS-Muenzen(aktStufe); end end end end end