mögliche Summen von n Zahlen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
Hi Leute,
folgendes Problem:
ich will aus einer Anzahl von 0-n Zahlen alle möglichen Kombinationen finden, deren Summen genau einen bestimmten Wert x ergeben.
Was ich bisher mache:
Wenn es keine oder nur eine Zahl gibt ...trivial.
Wenn die Summe aller Zahlen =< x ist...trivial.
Ansonsten überprüfe ich ob es genau die benötigte Zahl x gibt und schmeiße Zahlen die höher sind raus.
Dann wirds schwieriger.
Ich denke es wäre vernünftig die Zahlen von groß nach klein zu ordnen. Die Größte mit allen anderen durch zu probieren, sie dann rauszuschmeißen und mit dem Rest wieder genauso vorzugehen.
Aber so richtig zielstrebig bin ich noch nicht...
angenommen:
ich hab die Zahlen 6 5 5 3 2 1 1
mein zu suchender Summand x ist 9
6+5
6+5
6+3<gefunden
6+2 (kleiner 9...nächste Zahl dazu)
6+2+1 <gefunden
6+2+1 <gefunden
6+1
6+1+1
6+1
6 weg
DIE FRAGE:
immer wenn ich unter x bleibe muss ich alle möglichen Kombinationen
finden um weiter zu summieren.
Da ich nicht weiß wieviele Zahlen ich schlußendlich summieren muss, muss es wohl irgendwie rekursiv passieren.
Vielleicht hat jemand hier eine gute Idee die (restlichen) Zahlen-Kombinationen zu finden.
Ach ja und
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
:)
lg Andi
|
|
| |
|
Hallo Andi, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
mal eine grobe Skizze des Ablaufs:
0. Vorab die Zahlen nach Größe absteigend in einem Feld anordnen. Zielvorgabe (bei dir 9) sei z.
1. Zwischensumme 0 setzen, Index (hier: i) 0 setzen
2. Index erhöhen. Indizierte Zahl zur Zwischensumme addieren.
3.1. Ist Zwischensumme gleich z? --> Lösung
3.2. Ist Zwischensumme kleiner z? --> zu 2.
3.3. Ist Zwischensumme größer z? Indizierte Zahl wieder abziehen, zu 2.
Jetzt musst Du noch drei wesentliche Dinge überlegen:
a) Wie speicherst Du eigentlich eine gefundene Lösung?
b) Wann und wie geht das Verfahren zu Ende?
c) Wie vermeidest Du gleiche Lösungen? Bei den gegebenen Zahlen gibt es z.B. zweimal die Lösung 6,2,1 - nämlich einmal mit der ersten und einmal mit der zweiten 1. Trotzdem musst Du beide berücksichtigen, weil Du sonst 5,2,1,1 nicht findest.
Hilft Dir das erstmal weiter?
Grüße
reverend
|
|
|
| |
|
Hi reverend!
Ja anscheinend ist mir die Lösung jetzt klar.
Dein Satz "Indizierte Zahl wieder abziehen" hat in meinem Denkkonstrukt noch gefehlt!
Also wenn ich einen Stack baue, auf den ich die Zahlen lege passiert folgendes:
6
65>zu hoch
6
65>zu hoch
6
63>Lösung
6
62
621>Lösung
62
621>Lösung
62
6
-> 6er weg
5
55> zu hoch
5
53
532> zu hoch
53
531>Lösung
53
531>Lösung
53
5
-> 5er weg
usw.
Das ist doch Dein Vorschlag oder?
Das müsste mir alle möglichen Kombinationen liefern?
Super, danke!
|
|
|
| |
|
ah, nein...
bei meinem Stack fehlt die Lösung 5211
Da muss ich nach dem 3er noch weitergehen...na ich werds schon irgendwie hinkriegen... *weiterdenk*
|
|
|
| |
|
Hallo Andi,
> ich will aus einer Anzahl von 0-n Zahlen alle möglichen
> Kombinationen finden, deren Summen genau einen bestimmten
> Wert x ergeben.
Ich würde sagen, das ist eine ![[]](/images/popup.gif) Variante des Untermengensummen-Problems.
Gruß V.N.
|
|
|
| |
|
Hi rev,
> Ja, das ist es. Aber in einer so begrenzten Form ist es
> doch viel netter, selbst an einer Lösung zu arbeiten.
Ja eigentlich schon. :) Vor allem, weil man bei einer schnellen Lösung "die Weltordnung auf den Kopf stellen könnte". ![[happy]](/images/smileys/happy.gif "[happy]") . (Siehe insb. Seite 6 beim Link)
Gruß V.N.
|
|
|
| |
|
Danke vielmals für den link!! Ist natürlich sehr spannend zu wissen wie das Problem heißt...NP-Vollständigkeit, Rucksackproblem... ich habs befürchtet ;)
|
|
|
|
