Blog

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