PDA

Vollständige Version anzeigen : Welche X Zahlen aus einer Liste ergeben Summe Y


Andreass
22.02.2008, 11:17
Hallo,

bekomme ich folgende Problemstellung mit Excel gelöst ?

Ich habe eine Liste mit einer Buchungsnummer und einem Betrag (ca. 800 einzelne Zeilen) und möchte nun herausfinden welche x Einzelbeträge eine bestimmte Summe Y ergeben.

Beispiel

Liste:
4711 1,00 EUR
4712 3,00 EUR
4713 5,00 EUR

Summe soll 8,00 sein, so dass das Ergebnis Zeile 2 und 3, also die Buchungsnummern 4712 und 4713 sein sollte.

Wenn es mehrere Lösungen gibt, sollten die auch irgendwie gekennzeichnet sein.
Es müsste doch möglich sein, per VBA alle möglichen Kombinationen rechnen zu lassen oder ?

Kann mir jemand einen Ansatz hierfür geben, denn ich bin im Moment etwas planlos.

Vielen Dank erstmal

Andreass

luckybaer
22.02.2008, 11:26
Moin.

Meines Erachtens brauchst Du zunächst ein oder mehrere Kriterien um eine Formel aufzustellen. Soll z.b. immer Buchungsnummer x und die nachfolgende summiert (also die Beträge) werden oder was / welches sind die Kriterien?

Gruß

luckybaer

Andreass
22.02.2008, 11:44
Das Ergebnis kann ja 1 - n Buchungsnummern sein, wobei n die Anzahl der Zeilen ist.

Man müsste also hergehen und die erste Zeile nehmen und mit der Gesamtsumme vergleichen, stimmt es nicht überein Zeile 1 und zwei, dann 1 und 3 bis 1 und n.
Danach mit 3 Zahlen weiterrechnen, also 1, 2 und 3, dann 1, 2 und 4 usw.

Das wäre mein theoretischer Ansatz. Wie aber weiter ?

Andreass

Berti_S
22.02.2008, 11:54
Wie hoch ist denn der Anteil derjenigen Zeilen, deren Wert kleiner als dein gewünschtes Summations-Ergebnis ist ?

Wenn dies nahe bei deinen 800 liegt, kannst du dein Problem m.E. vergessen, zumindest wenn du alle möglichen Kombinationen haben willst.
Die Varianten steigen schnell ins Uferlose...

Berti

luckybaer
22.02.2008, 12:03
Ich glaube, ich habe dein Problem noch nicht verstanden. Kannst Du das noch mal ausführlicher schildern?
Was soll das Ergebnis sein

Gruß
luckybaer

Andreass
22.02.2008, 12:04
Das kann ich nicht sagen, ich schätze aber, dass der Anteil sehr hoch ist (>85%). Es geht auch nicht immer um die gleiche Liste, es gibt auch Listen mit weit weniger Zeilen, die 800 sind wohl schon ein Extremwert.

Ich denke, dass sich die Anzahl der Varianten in Grenzen hält, da es sich um einzelne Rechnugsbeträge handelt und diese doch sehr unterschiedlich sind. Aber besser gezielt 10 oder 20 Varianten nachprüfen (das ist möglich in der Fibu) als "planlos" von Hand Zahlen zu addieren und hoffen, dass man irgendwann auf den Betrag kommt.

Andreas

EarlFred
22.02.2008, 12:10
Hallo zusammen,

Excel hat doch das richtige Werkzeug gleich dabei: Das Add-In "Solver".

Habe mal eine Beispieltabelle angehängt - das Know-How ist hier im Forum schon zu finden, ich habe den Artikel aber grad nicht mehr zur Hand und bin zu faul zum Suchen ;)

Das Add-In muss aktiviert werden in Excel und bei Bedarf auch in VBA (Verweise). Zudem bitte einen Blick auf die Solveroptionen werfen.

Einziger Haken: Ich bin noch nicht dahinter gekommen, wie man damit mehrere Lösungsvarianten anzeigen lassen kann, ohne unschöne Krücken zu verwenden.

Grüße
EarlFred

P.S.: In der Zelle A4 könnte man auch eine 4 eintragen, dann klappt es auch häufiger ;)

Andreass
22.02.2008, 12:16
Ahhh, Solver kenn ich doch, warum hab ich da nicht dran gedacht. Werd ich gleich mal ausprobieren.

Andreass

rastrans
22.02.2008, 12:17
Coole Aufgabe! :)

@luckybaer
Nimm mal eine Menge G der Zahlen 1 bis 20. Jede Zahl kommt nur einmal vor!
Nun hast du das Ergebnis 42 (Die Antwort der Fragen aller Fragen!;))

Welche Zahlen aus der Menge G musst du nun summieren um auf das Ergebnis zu kommen? Die Untergruppe G(x) darf zwar immer alle Elemente aus G enthalten, jedoch jedes Element nur einmal!

Erste Lösungen:
G(1) = {20,19,3}
G(2) = {20,19,2,1}
G(3) = {15,19,6,2}
...
(Mengenlehre fand ich in der zweiten Klasse schon prima. Wird heute einfach zu sehr vernachlässigt!)

---

Lösungsansatz:
Das sollte doch wohl über Rekursion funktionieren. Elemente der Hauptgruppe sind dann alle Zahlen die kleiner sind als mein Ergenbis. Wenn ich erst einmal mindestens ein Ergebnis gefunden habe, muss dieses auch weider aufgeteilt werden. Siehe oben bei G(1) und G(2). Hier habe ich die 3 wieder aufgeteilt in 1 und 2.

Viele Grüße
rastrans

Styrkar
22.02.2008, 12:21
Hi,

das Problem gabs schon mal:
http://www.ms-office-forum.net/forum/showthread.php?t=203919

Sebastian Schulz
22.02.2008, 12:21
Hallo,

ein ähnliches Thema wurde hier schonmal behandelt.
http://www.ms-office-forum.de/forum/showthread.php?t=217654&highlight=Solver

EarlFred
22.02.2008, 12:23
Hi Sebastian, hi Styrkar,

diese Artikel meinte ich ;)

Grüße
EarlFred

Berti_S
22.02.2008, 13:06
Hallo rastrans,

die Hauptmenge besteht sicherlich aus allen Zeilen, welche kleiner gleich dem gewünschten Ergebnis sind.
Aber eine Aufteilung (aus 20 mache 19, 1) oder (17, 2, 1) dürfte hier wohl nicht in Frage kommen - ich kann ja keinen Buchungsbetrag splitten. Auch die Forderung nach "jeder Wert nur einmal" dürfte hier nicht funktionieren.

Berti

rastrans
22.02.2008, 17:50
Mit Wert nur einmal meinte ich, jedes Element der Gruppe nur einmal.

Natürlich kannst du nicht einen Betrag einfach so splitten. Aber wenn du einen Gesamtbetrag von 42EUR hast und Buchungsbeträge von 3EUR, 2EUR und 1EUR, dann kannst du doch die 3EUR doch noch in 1 und 2 EUR aufteilen!?!

ransi
22.02.2008, 18:34
HAllo andreas

(ca. 800 einzelne Zeilen)

Maximal wieviel Summanden können denn den Endbetrag ergeben ?
Bei 800 zellen wären das schlimmstenfalls 800.
Da bräuchtest du dann aber vieeeeel Zeit damit ein Code alle Kombinationen abarbeiten kann....

Kannst du das auf eine Anzahl Summanden begrenzen?

ransi

Andreass
25.02.2008, 13:41
Hallo an alle,

vielen Dank für eure Gedanken zu diesem Thema.

Ich habe es am Wochenende geschafft mein Problem mit Bordmitteln (sprich über unsere Fibu) zu lösen.

Vielen Dank nochmals.

Andreass

bretsch
16.12.2018, 13:58
Hallo,
ich suche aus insegesamt 83 Zahlen alle Kombinationen welche eine bestimmte Summe mit exakt 38 werten ergeben, mehrere Kombinationen sind möglich und ich möchte gerne alle möglichen Kombinationen anzeigen lassen.
Mit hilfe des Solvers bekomme ich eine mögliche Kombination raus, brauche aber alle.
Kann mir wer weiterhelfen?
Merci schon mal.

aloys78
16.12.2018, 14:35
Hallo,
Kann mir wer weiterhelfen?
Sollte man da nicht die 83 Zahlen (am besten in einer Excel-Tabelle) kennen ?

Gruß
Aloys

Der Steuerfuzzi
16.12.2018, 15:57
Warum kapert man dafür einen über 10 Jahre alten Thread?
Dafür macht man einen neuen auf!

Oge
16.12.2018, 19:49
Hallo b...,

ich hoffe du hast genug Zeit. ;)

Bei 83 Zahlen gibt es ca. 10^24 mögliche Kombinationen mit 38 Zahlen.
Auf meinem Rechner würde es mit Excel ca 1 Milliarde Jahre dauern alle Kombinationen zu prüfen.

Aber wenn dein Rechner 1.000 mal schneller ist, sind es ja nur noch 1 Million Jahre.

In der Anlage eine VBA-Programm mit dem in einer begrenzten Zeit versucht wird passende Kombinationen zu finden.

Sulprobil
16.12.2018, 21:45
Hallo,

Ich bin mit Michael Sch.'s Lösung immer gut gefahren:
http://www.sulprobil.com/Get_it_done/IT/Excel_Fun/Excel_VBA/Accounts_Receivable_Problem/accounts_receivable_problem.html

Viele Grüße,
Bernd P