Wie finde ich die passende Zahlenkombination?
Ich habe 23 bestimmte Zahlen (Siehe Foto) und ich muss beliebig viele davon addieren um auf das Ergebnis 12.725,57 zu kommen. Wie muss ich vorgehen, um die passende Kombination zu finden?
Es ist möglich, dass es keine passende gibt.
*Jede Zahl kann nur einmal verwendet werden!
Darfst du die Zahlen auch doppelt verwenden?
Brauchst du die Lösung, oder einen Weg das mit anderen Zahlen wieder tun zu können?
Nein jede Zahl kann nur einmal verwendet werden. Aber guter Einwand!
11 Antworten
Das Problem das du hier vorliegen hast, ist ein Subset Sum Problem, du hast N Gegenständedie jeweils ein Gewicht (hier der Preis) haben, sowie ein Maximalgewicht, der nicht überschritten werden darf.
Das Ziel ist, so nah wie möglich an dem Maximalgewicht (also die genannte Summe) zu kommen, ohne dass es überschritten wird.
Wenn es möglich ist, exakt das Maximalgewicht zu erreichen, dann hast du deine Lösung.
Das Problem ist, dass dieses Problem NP-Volständig ist, und keine Triviale Lösung hat. Du musst also es entweder mit einer Programmiersprache umsetzten, oder per Hand bestimmen. (Jede Teilmenge zu testen ist keine Option, da es 2^N Teilmengen gibt)
Zur Umsetzung gibt es mehrere Möglichkeiten die hier aufgelistet sind. Per Hand wird es wohl zu schwer sein, weswegen du es programmieren müsstest.
Also ich habe Mal einen der Algorithmen drauf angewendet, das Programm brauchte nur 2 Sekunden oder so, jedoch ist das Ergebnis das rausgekommen ist, 12725.45, der exakte Betrag lässt sich also nicht erreichen, falls ich alles richtig abgetippt habe.
Hallo, ich habe mein Makro so weit optimiert, dass es nur mehr ein paar Minuten braucht, um die Lösung zu finden. Habe das auch mit deinen und anderen Zahlen erfolgreich getestet, aber dein Beispiel hat keine Lösung. Kannst gern selber probieren, Ziffern in A1-A23 aufsteigend sortieren und Zielwert in C1, hier ist der Code:
Sub ausziffern()
Application.Calculation = xlCalculationManual
Dim kum(100)
Ziel = Range("C1")
For i = 2 To 100
If Cells(i, 1) = 0 Then x = i - 1: Exit For
s = s + Cells(i - 1, 1)
kum(i) = s
Next i
For i = 2 ^ x - 1 To 1 Step -1
100 s = 0: k = i
For j = x - 1 To 0 Step -1
d = 2 ^ j
If Int(k / d) = 1 Then
k = k - d
s = s + Cells(j + 1, 1)
Cells(j + 1, 2) = "x"
If s > Ziel Then i = i - d: GoTo 100
If s + kum(j + 1) < Ziel Then i = i - d: GoTo 100
Else
Cells(j + 1, 2) = ""
End If
Next j
If s = Ziel Then Exit For
Application.StatusBar = i
DoEvents
Next i
Application.Calculation = xlCalculationAutomatic
Application.StatusBar = False
End Sub
Erstmal die zahlen nach Größe sortieren, alles was > als die Lösung ist, fliegt raus.
(Man kann noch so viel addieren, wenn zu groß, dann zu groß.)
In Excel dann, in spalte 2, alle Zahlen aus spalte 1 mit der kleinsten zahl addieren.
Was zu groß ist fliegt raus.
Jetzt bist du die großen unmöglichen zahlen schon mal los.
dann mal die kleinen zahlen solange addieren bis du über die 12k lösung kommst.
Jetzt hast du ein feeling dafür wieviele zahlen es maximal sein können.
Und dann würde ich mich mit teil tabellen der lösung annähern, oder feststellen das es nicht geht.
Es ist keine gute Lösung bei noch größeren Zahlen oder mehr Einzelzahlen.
Aber ohne Programmierung und wenn man nur wissen will, ob und welche zahlen die lösung ergeben ist es ein überschaubarer Aufwand.
Oder jemand kommt mit einer bereits vorhandenen Formel dazu um die Ecke.
Jap und es können maximal 13 zahlen addiert werden.
ich hab das versucht ähnlich wie von "Zalto" gesagt weiter zu führen, aber das ist mir bei 3 Summanden schon aus dem Ruder gelaufen.
Ständig überlegt man ob die Basiszahlen richtig abgetippt sind,
ob man beim kopieren der Bereiche fehlerfrei gearbeitet hat und am Ende hast du zwar alle möglichkeiten ausgeschöpft aber wenn es keine "Lösung" gibt, fehlt irgendwie die Belohnung. So als Bestätigung das man es richtig gemacht hat.
Nächste Idee wäre dann, alle möglichen Kombinationen ausrechnen zu lassen und diese Liste nach den 12.725,57€ zu durchsuchen.
Also: AB bis AZ, ABC-XYZ, usw.
(ich bin raus) :-)
Kennst du bestimmte Programme und geht es auch Excel?
Programme kenne ich nicht, aber ich habe mal mit dem SOLVER von Excel was gebastelt:
Allerdings musst Du da die 16 noch von Hand eingeben.
In A würdest Du Deine Werte eingeben und in B stünden zu Anfang nur Nullen.
Findet aber nur EINE Möglichkeit und der Solver ist meiner Erfahrung nach auch "mit Vorsicht zu genießen.
OHNE GEWÄHR!
Vielen Dank. Aber er verwendet bei mir Dezimalzahlen in Zeile B, obwohl ich dieselben Nebenbedingungen habe
Das kann eigentlich nicht sein.
Du musst bei Nebenbedingung --> Hinzufügen B1:B10 markieren und dann
"int"
auswählen! Dann darf er eigentlich nur Ganze Zahlen nehmen.
Ich würde den Wert a aus jeder Zeile auch nochmal in eine Kopfspalte als b übertragen und dann in dieser Tabelle die Summe a+b aus Kopfspalte und Kopfzeile berechnen lassen.
Sind 23*23 Werte. Davon die Diagonale streichen (a+a ist ja nicht erlaubt) und entduplizieren (a+b ist auch b+a). Alle Summen über 12.725,57 kannst Du auch gleich streichen.
Was übrig bleibt, wieder, zusammen mit den ursprünglichen Werten, in die Kopfspalten und Kopfzeilen verteilen und die Übung wiederholen.
Das werden sehr schnell sehr viele Kombinationen ("kombinatorische Explosion"), aber solange es nur drei oder vier Summanden sind, sollte das zum Erfolg führen.
Mit einem "richtigen" Programm in VBA sollten auch noch ein paar mehr Summanden möglich sein.
Selbst wenn ich mit deiner Methode die unmöglichen Zahlen rausnehme, sind es immer noch 22 mögliche Zahlen. Ich habe auch schon den zweiten Schritt gemacht aber die Kombinationsmöglichkeiten sind leider zu groß.