Problem der Erbteilung ?

[-lx-]

Hallo.

Ich habe von meiner Tante eine Truhe geerbt, die ich mir mit meinem Bruder teilen muss.
In der truhe befinden sich 5 Geldstücke mit den Werten 5, 9, 1, 3 und 8.

Nun ist es so, dass wir erst dann unser Erbe erhalten, wenn wir den Geldbetrag gerecht unter uns aufteilen. Sollten wir das nicht schaffen, löst es sich in Luft auf.

Rechnerisch kommt man leicht drauf, wieviel jeder von uns bekommen kann:

5 + 9 + 1 + 3 + 8 = 26
26 div 2 = 13

D.h. jeder muss einen betrag von 13 erhalten.


So nun ist aber die Frage, in welchen Kombinationen die einzelnen Geldstücke verteilt werden müssen, um auf den Betrag von 13 zu kommen.

ich denke Ihr habt shcon gemerkt dass es sich um eien Aufgabe handelt und nicht um eine "wirkliches" Erbe ;)


Zum programmieren:
Mir ist klar, dass man immer einen Wert zum anderen bzw zur bereits vorhandene Menge hinzu addieren muss und dann überprüft man, ob man unterhalb, gleich oder oberhalb der 13 liegt.
Fangen wir mal an:
5 < 13
5 + 9 > 13
5 + 9 - 9
5 < 13
5 + 1 < 13
5 + 1 + 3 < 13
5 + 1 + 3 + 8 > 13
5 + 1 + 3 + 8 - 8
5 + 1 + 3 < 13


aber was nun ?

Das muss ja via Backtracking und Rekursion gelöst werden. Ich komm nur nicht ganz dahinter wie ich weiter machen muss.


Über Hilfe würde ich mich sehr freuen. Vll. hat dieses Verfahren eine speziellen Namen denn unter "Backtracking Erbproblem" finde ich nichts.

Wäre dies nicht eig. eine Art der Permutation ?




mit freundlichen Grüßen

Alex

[Der_Unwissende]

Zitat:

Zitat von -lx-

Zum programmieren:
Mir ist klar, dass man immer einen Wert zum anderen bzw zur bereits vorhandene Menge hinzu addieren muss und dann überprüft man, ob man unterhalb, gleich oder oberhalb der 13 liegt.

aber was nun ?

Das muss ja via Backtracking und Rekursion gelöst werden. Ich komm nur nicht ganz dahinter wie ich weiter machen muss.

Hi,
natürlich merkt man recht schnell, dass das eine Aufgabe ist. Allerdings fehlt ein wenig die Erklärung was du schon über Backtracking weißt?

Zitat:

Zitat von -lx-

Wäre dies nicht eig. eine Art der Permutation ?

Backtracking ist nur eine bestimmte Art alle Permutationen zu bilden. Du gehst dabei einfach systematisch vor und kannst aufhören, sobald du eine Permutation gefunden hast, die gut genug ist. Häufig möchtest du gar nicht die einzigste Optimale Lösung berechnen (einfach nur weil das viel zu lange dauern würde), dann kannst du mit ein paar geschickten Opitmierungen und Überlegungen und ggf. etwas Backtracking eine für dich ausreichend gute Lösung finden.

Backtracking geht dabei den Weg, dass du etwas versuchst und schaust ob es passt. Du merkst dir praktisch, wo du gerade bist und versuchst alle Möglichkeiten, die von diesem Punkt aus möglich sind. Findest du einen nächsten Schritt, bist aber noch nicht fertig, so gehst du in diesem Schritt genauso vor. Jetzt gibt es zwei Möglichkeiten: Eine Lösung führt zu dem Ergebnis -> Du bist fertig. Die Lösung führt nicht zum Ergebnis -> Du gehst einen Schritt zurück und machst mit der nächsten Möglichkeit weiter.

Das ganze ist rekursiv einfach nur sehr einfach zu programmieren. Hier liegen dann klar die Vorteile der Rekursion.
An sich ist die Idee nicht, dass du etwas zu addierst und wieder abziehst, sondern dass du die erste Zahl nimmst und nun schaust, was hier möglich ist. Du merkst dir also die erste Zahl und hast jetzt die Möglichkeit eine der anderen Zahlen zu addieren.

Stell dir einfach vor, dass du die Aufrufe benennst. Im ersten Schritt (Aufruf A) geht es darum eine Zahl zur 5 zu addieren. In Frage kommt die 9, 1, 3 und 8. Hast du eine Zahl addiert, gibt es drei Möglichkeiten:

1. Die Summe ist 13, du bist fertig
2. Die Summe ist kleiner 13, du machst rekursiv weiter (neuer Aufruf)
3. Die Summe ist > 13, du gehst springst zum letzten Aufruf zurück

Für Aufruf A gibt es 4 Zahlen, die du betrachten kannst. Du fängst also mit der 9 an und nun ja, es klappt nicht. Also bleibst du in Zustand A und machst mit der 1 weiter. Wie du ja gesagt hast ist 5 + 1 < 13. Damit rufst du (rekursiv) die gleiche Funktion auf (Aufruf B). Aufruf B besteht jetzt aus der Zahl 6 und es kann noch die 3 oder 8 addiert werden.
Addierst du die 3, ist der Wert < 13 -> Rekursiver Aufruf (Aufruf C). In C hast du den Wert 9 und kannst noch die 8 addieren. Ja, 8 addieren bringt dich zu größer 13. Da es keine andere Zahl mehr gibt, die du addieren kannst, ist C kein Weg der zum Ziel führt. Also gehst du zurück in Zustand B.
B hatte die Zahl 6 und die Möglichkeit 3 oder 8 zu addieren. Das Addieren von 3 hast du gerade betrachtet, folgt also das Addieren von 8, geht natürlich auch nicht. Also zurück zu A. Hier hattest du die 5 und schon versucht die 9 und die 1 zu addieren, also machst du jetzt mit der 3 weiter...

Ich hoffe du hast das System grob verstanden. Das ganze kann man wirklich einfach in einer Rekursion verpacken. Da hast du gerade den Vorteil, dass so ein rekursiver Aufruf aut. dazu führt, dass der alte Zustand behalten wird. Versuch es einfach mal und frag nochmal nach, wenn etwas unklar ist.

Gruß Der Unwissende

PS: Nach einer einfachen Lösung für genau das Problem zu suchen hilft dir nicht viel, in der Klausur (aber auch in vielen Programmen) kannst du schnell auf eine andere Form von Backtracking treffen. Einmal verstanden ist das System immer gleich und gehört und wirklich nicht schwer!

[Blackheart]

Vieleicht würde es helfen die Zahlen vorher zu sortieren und dann zu vergleichen.

9 + 8 + 5 + 3 + 1 = 26 / 2 = 13
9 + 8 > 13 (8 fliegt raus)
9 + 5 > 13 (5 fliegt)
9 + 3 < 13 (3 bleibt)
9 + 3 + 1 = 13 (richtig)

[Thorben_K]

wie das geht weiss ich leider nichts, aber das ist das sogenannte "[dp]Rucksack probleme"[/dp], da habe ich vor einigen tagen erst ein lösungs ansatz bzw vorschlag gesehen

edit : Webseiten-Titel vll hillft dir das ja


gruss Thorben

Edit2: nach nochmaligen lesen weiss ich net ob das stimmt, was ich geschrieben habe, na ja kannst es dir ja trotzdem mal anschauen :D

[Der_Unwissende]

Zitat:

Zitat von Thorben_K

wie das geht weiss ich leider nichts, aber das ist das sogenannte "[dp]Rucksack probleme"[/dp], da habe ich vor einigen tagen erst ein lösungs ansatz bzw vorschlag gesehen

Das wäre aber eine sehr sehr spezielle Variante des Rucksackproblems. Immerhin soll hier ein exakter Wert erreicht werden. Beim Rucksackproblem handelt es sich vielmehr um ein Optimierungsproblem (einer der Fälle, in dem man nur das Beste sucht).
Selbst im speziellen Fall, dass das Gewicht dem Wert gleicht kann es sein, dass die optimale Lösung nicht das volle Gewicht ausnutzt. Sagen wir man hat ein max. Gewicht von 3 und zwei Teile, die gerade 2 wiegen (und den gleichen Wert haben!).
Natürlich kann man auch das spezielle Rucksack-Problem (bei dem halt Gewicht = Wert) ist verwenden, es lösen und wenn das max. Gewicht hier dem halben Erbe und die Lösung des Rucksackproblems als Wert halt auch dem halben Erbe entspricht, super dann hat man eine Lösung. Wäre allerdings eine vollkommen unnötige Reduktion (auf ein imo nicht gerade leichteres Problem). Durchaus möglich, aber eben mehr arbeit :wink:

[-lx-]

Hallo und herzlichen Dank für eure Antworten !! =)


Wie schon gesagt ist Backtracking eien Verfahren des Ausprobierens. D.h. sollte es nicht mehr weiter gehen, geht man sowiet zurück, bis man wieder eine Möglichkeit zur Auswahl hat, die man noch nicht ausprobiert hat - soweit die Theorie ;)

Beispiele wie das 8-Damen problem oder den Weg aus einem Labyrinth zu finden, sind in der theorie ganz simpel. Nur in der Ausführung hapert es - zumindest bei mir. Ob das normal ist.. weis ich nicht.


Hier mal ein Stück Code, der jedoch noch nicht das gewünschte Ergebnis ausspuckt:

Delphi-Quellcode:

procedure SucheLoesung(i, Erbhaelfte: Integer) ;
var j: Integer ;
    begin
      If i < length(Feld) Then
          begin
            Erbe:= Feld[i] ;
            For j:= i To length(Feld) - 1 Do
                begin
                  If (Erbe + Feld[i+1]) < Erbhaelfte Then
                      begin
                        SucheLoesung(i+1, Erbhaelfte) ;
                      end
                  Else if (Erbe + Feld[i+1]) = Erbhaelfte Then
                end;
            Erbe:= Erbe + Feld[i] ;
          end;
      Edit1.Text:= IntToStr(Erbe) ;



    end;

Hier handelt es sich um die Procedure SucheLoesung. Ihr wird der Parameter 1 für i übergeben und Erbhaelfte erhält den Wert des habeln Erbes - soweit es einen gibt.

Meiner Meinung nach muss es mindestens eine For-Schleife geben. Eien weitere Frage ist, ob man erst überprüft ob ein erneuter rekursiver Aufruf sinnvoll ist O D E R ob erst in einem erneuten rekursiven Aufruf geprüft wird, ob dieser sinnvoll war oder nicht. Desweiteren ist mir nie so wirlich klar - bei der Rekursion - wo genau die Werte zum Gesamtergebnis zusammengetragen werden. Also ab welcher Position.

Sorry dass ich frage, aber ich finde Rekursion schon etwas komplex und "verdreht".





Mit freundlichen Grüßen

[Hawkeye219]

Hallo Alex,

es handelt sich hier um ein 2-Personen-Nullsummenspiel, bei dem ein Betrag X vollständig zwischen zwei Personen aufgeteilt wird. Eine Person kann jede der 5 Münzen besitzen oder nicht besitzen - es gibt also 32 Möglichkeiten für die Aufteilung.

Die Lösung kann auch ohne Rekursion mit einer einfachen Schleife ermittelt werden, wobei man den Schleifenzähler als Bitvektor auffaßt. Ein gesetztes Bit bedeutet "Münze erhalten", ein gelöschtes Bit bedeutet "Münze nicht erhalten". Bei jedem Schleifendurchlauf kann auf diese Weise der Anteil einer Person berechnet werden. Entspricht der doppelte Anteil der gesamten Erbsumme, war die Aufteilung gerecht, und es wurde somit eine Lösung gefunden.

Gruß Hawkeye

[-lx-]

Jedoch soll es mitHilfe der Rekursion und des Backtrackings gelöst werden.


Eig. wäre doch eien Funktion viel besser geeignet, oder ?


Wie komme ich denn wieder con Aufruf C zu Aufruf B und A zurück ?

[Cöster]

@ Hawkeye: Würde sich das nicht bei einer größeren Anzahl von Münzen negativ auf die Rechenzeit auswirken? Denn wenn ich dich richtig verstehe, willst du alles ausprobieren.

Zitat:

Zitat von -lx-

Jedoch soll es mitHilfe der Rekursion und des Backtrackings gelöst werden.


Eig. wäre doch eien Funktion viel besser geeignet, oder ?


Wie komme ich denn wieder con Aufruf C zu Aufruf B und A zurück ?

Widerspricht sich das, Rekursion + Backtracking und Funktion? Von Aufruf B gelangst du automatisch zurück zu Aufruf A: A ruft B auf, sobald B fertig ausgeführt ist, bist du wieder in A.

[-lx-]

Habs gelöst.


Ich weis nur noch nicht recht wieso Oo

Wäre für eine Erklärung seeehr dankbar.


Habs auch mit verschiedenen Werten versuchst.

Delphi-Quellcode:

procedure SucheLoesung(i, Erbhaelfte: Integer) ;
var j, tmp: Integer ;
    begin




      For j:= i To length(Feld) Do
          begin
            tmp:= Feld[j] ;
                  If (Erbe + tmp) = Erbhaelfte Then Edit1.Text:= 'Gefunden _ ' + IntToStr(Erbe+tmp)
            Else  If (Erbe + tmp) < Erbhaelfte Then
                      begin
                        Erbe:= Erbe + tmp ;
                        If i < length(Feld) Then SucheLoesung(i+1, Erbhaelfte) ;
                      end;
          end;



    end;

Edit: Der funktioniert doch nocht nicht richtig -.- versucht mit: (17,42,7,4,16) ;


Edit2: Moment. Man kann ja nicht x beliebige Werte in einer x beliebigen Kombination verwenden. Diese müssen sich schon so summieren lassen - also die einzelnen Felder des Arrays, das sie sich in 2 gleich große Gruppen aufsaplten lassen. Achsoooo... mh


Edit3: Nein also richtig funktioniert es noch nicht. Wenn ich 8,3,7,9,1 eingebe, gibt er 14 aus. Schreibe ich jedoch 1,9,7,3,8 - also rückwärts - dann gibt er garnichst aus.


Edit4: Ich habe nun folgende Zeiel hinzugefügt: Erbe:= Erbe - tmp ;
Und zwar habe ich sie nach dem rekursiven Prozeduraufruf, innerhalb der If-Abfrage reingepackt. Meien überlegung ist, sollte er einmal dennoch größer werden, fällt er an den Punkt des prozeduraufrufes zurück. Da die vorherige Addition falsch war, subtarhiert er wieder den letzten Wert vom Gesamtergebnis.


Ist das denn so richtig ? Oder geht es noch einfacher und simpler (dennoch mittels Rekursion und Backtracking) ?