_Rhodan_
Grünschnabel
Dabei seit: 03.02.2013
Beiträge: 4
|
|
Komplexität Erbteilproblem |
|
Hi, ich sitze gerade über dem Erbteilproblem, d. h. ich möchte eine Menge von Münzen mit unterschiedlichem Wert gleichmäßig aufteilen. Das Problem an sich habe ich mit Hilfe von Backtracking gelöst - soweit gut.
Nun denke ich über die Komplexität dieser Suche nach einer Lösung bzw. nach allen Lösungen nach. Das Problem dürfte eine exponentielle Laufzeit haben - dies leite ich mir her, indem ich mir Bäume für 1, 2, 3, 4 ... Münzen aufzeichne und überlege, wie viele Zweige ich jeweils mit unterschiedlichen Lösungen erzeugen kann ...
... nur, wie kann ich das mathematisch herleiten ?
Kann mir da jemand helfen, oder hat etwas, wo ich dies genauer nachlesen kann?
Viele Dank im Voraus!!
|
|
27.01.2015 18:28 |
|
|
|
Wow, google findet nur 2 Treffer zu "Erbteilproblem". Ich habe davon auch noch nie etwas gehört.
Für Münzen und Erben hast du Verteilungsmöglichkeiten.
__________________ Syntax Highlighting fürs Board (Link)
|
|
27.01.2015 19:19 |
|
|
_Rhodan_
Grünschnabel
Dabei seit: 03.02.2013
Beiträge: 4
|
|
Naja, das mit dem exponentiellen Zusammenhang habe ich ja auch schon, ab wie erkläre ich mir das mathematisch ...
Das Erbteilproblem funktioniert im Prinzip wie alle Verteilungsprobleme - evtl. gibt es für dieses spezielle Problem auch noch ähnliche Namen.
|
|
27.01.2015 20:17 |
|
|
_Rhodan_
Grünschnabel
Dabei seit: 03.02.2013
Beiträge: 4
|
|
Hm, denke ich evtl. zu kompliziert ..., d. h. wenn das gesamte Erbe in zwei wertgleiche Teile aufgeteilt werden soll ... 2^n ...
|
|
27.01.2015 21:12 |
|
|
|
|
|