mir fällt kein besserer Name dafür ein… aber vielleicht gibts schon eine bessere Lösung dafür…
also man hat eine bestimmte Anzahl von Summanden und soll damit eine bestimmte Summe bilden, es reicht eine Lösung, aber es müssen alle möglichen gleich wahrscheinlich sein…
zB:
Summanden: 3 4 -6 2 1 1 -2 5
Summe: 10
Lösung (zB): 1+2+3+4
genauso wahrscheinlich soll aber auch zB 5-2+4+2+1 sein…
und der Aufwand sollte nicht proportional mit n! wachsen…
variante ich suche alle moeglichen und wahele dann eine zufaellig aus, nachteil aufwand steigt mit der anzahl der summanden
variante siehe unten: aufwand ist abhaengig von der differenz der summe zum durchschnitt der sumamnden, sonst konstant, nachteil: es werden nciht alle moeglichen loesungen gleichberechtigt…
ich ziehe von der gesuchten summe solange zufaellig gewaehlte summanden ab, die mich naeher an 0 bringen, bis ich bei 0 bin. wenn die aktuelle summe >0 , aber kleiner als der kleinste noch verfuegbare summand ist, gehe ich wieder einen schritt zurueck, sperre den dazugehoerigen summanden und suche weiter…
z.b.:
10 - 5 - 3 - 2
od:
10 - 4 - 5 - (-2) - 3
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
ja nicht schlecht…
aber es müssen alle möglichen Lösungen gleich wahrscheinlich sein…
so sind es nicht nur ungleiche Wahrscheinlichkeiten, sondern bei gleichen Angaben, kommt auch immer diesselbe Lösung raus…
um wenigstens allen möglichen Lösungen eine chance zu geben müsste man das kompliziert ausgleichen… ?
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
nein, es kommen nicht die selben raus, weil du die einzelnen summanden per zufall auswaehlst…
so sind es nicht nur ungleiche Wahrscheinlichkeiten, sondern
bei gleichen Angaben, kommt auch immer diesselbe Lösung
raus…
ja stimmt…
aber so kommt man schnell in eine Lage wo man die Summanden wieder streichen muss… oder auch nicht
zB
dasselbe wie oben
Summe: 10
Summanden: 3 4 -6 2 1 1 -2 5
die zufällig gewählten:
3+4+1+1… 9
wie könnte man von hier aus auf die (lange) Lösung: … +2+5-6 kommen?
oder wie baut man das in den Algorithmus ein?
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]