Welche Summanden bilden vorgegebene Summe?

Question

Hallo,

ich habe eine Zahlenreihe und möchte ermitteln welche Summanden aus dieser Reihe eine vorgegebene Summe 272,29 bilden (ggf. mehrere Möglichkeiten). Z.Bsp:

[list]A 15,00 272,29
B 17,85
C 17,85
D 107,10
E 96,99
F 46,00
G 98,00
H 64,00
I 180,00
J 35,50
K 51,00
L 38,50
M 90,00
N 30,00
O 38,00
P 56,00
Q 16,66
R 15,00
S 35,50
T 50,00
U 55,93
V 126,00
W 120,00
X 51,00
Y 51,00
Z 42,00
AA 115,50
AB 30,35
A 67,00
C 75,00
AD 42,25
AE 62,48
AF 52,00
AG 107,10
AH 55,00
AI 294,53
2446,09
[/list]
Ich kann mir eigentlich nur ineinander geschachtelte Schleifen vorstellen die alle Kombinationen prüfen müssten, was allerdings sehr schnell einen erheblichen Aufwand bedeutet. Hat jemand einen guten Tipp wie man die Sache angehen könnte?
Danke und Gruß A.

Answer 1

hi mr.k ^^

summanden jebseits von 100 sind von uebel
das waeren ja 2 hoch Anzahl Summanden an Möglichkeiten

ich glaub da muss eine bremse rein
mal schauen wann mein rechner zusammen bricht *g*
und ob der zusammenbruch kontrollierbar bleibt

gruss nighty

Answer 2

Hi Nighty. Es kommt natürlich immer auf die Struktur der Daten an. Je geringer die Zahlen auseinander sind, desto mehr Möglichkeiten gibt es. Habe grade mal aus Spaß versucht aus den Zahlen 1 bis 620 die Zahl 190.000 zu bilden. Bei 40.000 Ergebnissen, hab ich abgebrochen. Das ist ja auch nicht mehr übersichtlich händelbar. Sinn des Tools soll ja sein, dort, wo es nicht so viele Möglichkeiten gibt schnell eine Lösung zu finden.

PS: Eben kleinen Bug "Kompilierungsfehler" durch Entfernen von Option Explizit behoben. Versionsnummer nicht geändert. Somit sollten im Auswahlfenster die Checkboxen wieder aktivierbar sein. Datei an gleicher Stelle neu hochgeladen.

Gruß Mr. K.

Answer 3

hi Andreas und all ^^

ich glaub ich brauch ein bischen laenger(jede wette das das alter schuld ist (kicher kicher))

eine direkte indexerstellung ueber das binärsysten schlug schonmal fehl,ich schaffe es nicht ,es parallel zu halten

ich probier es nochmal in Verbindung zu dimensionsfeldern

ziel ist eine index Erstellung der Daten fuer einen schnellen vergleich

gruss nighty

Answer 4

Hallo,
nach meiner Rechnung gibt es insgesamt 435.897 Kombinationen für 5 Werte aus 37. Wenn du die Summe auf den Zielwert eingrenzt reduziert sich die Anzahl deutlich. Vlt. kannst du in deinem Code einen Zähler einbauen, um festzustellen, ob alle Kombinationen auch durchlaufen wurden...
VG A.

Answer 5

hi all ^^

war nur bisl spielerei,noch nicht optimiert

gruss nighty

Summanten ab zeile 2 spalte a
gesuchte summe zur zeit 33

Sub Summanten()
Range("B:C").Clear
Dim Lzeile As Long, BinZahl As Long, BinärIndex As Long, Zrng As Long
Dim BitIndex As Long, Puffer As Long, ZeilenIndex As Long
Dim Puffer1 As String
Lzeile = ActiveSheet.Cells(Rows.Count, 1).End(xlUp).Row - 1
ReDim daten(0 To 1, 1 To Lzeile) As Long
ReDim bdat(1 To 2 ^ Lzeile) As String
For Zrng = 1 To Lzeile
daten(1, Zrng) = Cells(Zrng + 1, 1)
Next Zrng
For BinZahl = 1 To 2 ^ Lzeile
bdat(BinZahl) = dec2bin(BinZahl)
If Len(bdat(BinZahl)) < Lzeile Then
For Zrng = 1 To Lzeile - Len(bdat(BinZahl))
bdat(BinZahl) = "0" & bdat(BinZahl)
Next Zrng
End If
Next BinZahl
For BinärIndex = 1 To 2 ^ Lzeile
For BitIndex = 1 To Lzeile
Puffer = Puffer + daten(Mid(bdat(BinärIndex), BitIndex, 1), BitIndex)
If daten(Mid(bdat(BinärIndex), BitIndex, 1), BitIndex) <> "0" Then Puffer1 = Puffer1 & " " & daten(Mid(bdat(BinärIndex), BitIndex, 1), BitIndex)
Next BitIndex
'gesuchte summe zur zeit 33
If Puffer = 33 Then
ZeilenIndex = ZeilenIndex + 1
Cells(ZeilenIndex, 2) = Puffer
Cells(ZeilenIndex, 3) = Puffer1
End If
Puffer = 0
Puffer1 = ""
Next BinärIndex
End Sub

Function dec2bin(ByVal lngZahl As Long) As String
If lngZahl > 0 Then dec2bin = dec2bin(lngZahl \ 2) & IIf(lngZahl Mod 2, "1", "0")
End Function

Answer 6

Hallo nighty,

also das ist bestimmt nicht nur ein bißchen Spielerei...!??? Ich finde das echt Klasse! Ich habe den Code mit einigen Varianten mal getestet und jedesmal ein befriedigendes Ergebnis erhalten!! Ich überschaue allerdings noch nicht, wieviel Varianten du rechnest und ob damit alle möglichen Kombinationen beachtet werden Habe aber wie immer volles Vertrauen in deine Arbeit!!
Toll, vielen Dank!!
Gruß A.

Answer 7

Hallo nighty,

wie verhält sich der Code bei Dezimalzahlen, zweistellig? Da habe ich noch keine Lösung gefunden.
Gruß A.

Answer 8

hi andres und all ^^

zu frage 1
es werden alle Möglichkeiten aufgelistet

zu frage 2
ob mit oder ohne kommastellen spielt keine rolle
da wir ja nach feldindex vergleichen

allerdings muss es exakt aufgehen,es erfolgt keine annaeherung

gruss nighty

Answer 9

hi Andreas ^^

eine annaeherung waere vielleicht in % angaben -/+ machbar
vielleicht so

ersetzen
33 ist die Gesamtsumme

If Puffer = 33 Then

durch
33 -5%/+5% ist die Gesamtsumme

If Puffer >= 33 - 33 / 100 * 5 And Puffer <= 33 + 33 / 100 * 5 Then

gruss nighty

Answer 10

Hallo nighty,

das mit den Dezimalstellen will mir nicht einleuchten.
wenn ich aus der Zahlenreihe die Summe 142,99 berechnen will (6. und 7. Element) erhalte ich kein Ergebnis.
15
17,85
17,85
107,1
96,99
46
98
64
180
In anderen Versuchen wurde dann auf ganze Zahlen "gerundet".
Gruß A.