Algorithmus lösung Summe Aufwand Summanden Summe bilden

Summandenproblem

Von: , Frage gestellt am Do, 23. Aug 2001

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...

4 Antworten zu dieser Frage

1. Antwort von nach 14 Stunden 0 hilfreich

   Re: Summandenproblem

   1. variante ich suche alle moeglichen und wahele dann eine zufaellig aus, nachteil aufwand steigt mit der anzahl der summanden
   
   2. 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]
   

   • Antwort von nach 15 Stunden 0 hilfreich

     Re^2: Summandenproblem

     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]
     

     • Antwort von nach 16 Stunden 0 hilfreich

       Re^3: Summandenproblem

       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...
       

       • Antwort von nach 18 Stunden 0 hilfreich

         Re^4: Summandenproblem

         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]
         

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!