Hallo,
ich suche einen Algorithmus, der aus einer gegebenen Menge natürlicher (nicht notwendigerweise unterschiedlicher) Zahlen diejenigen heraussucht, die eine vorgegebene Summe ergeben. Also z.B. gegeben seien die Zahlen (1, 1, 3, 17), die vorgegebene Summe sei 5, dann ist die Lösung (1, 1, 3).
Der konkrete Anwendungsfall ist: Ein Kunde hat im Laufe eines Monats n > 100 Rechnungen bekommen, die Gesamtsumme beläuft sich auf x €. Bezahlt hat er aber nur y €, d.h. einige Rechnungen sind unter den Tisch gefallen. Der einfache Weg der direkten Abklärung, welche Rechnungen er mit dieser Überweisung begleicht, ist vielleicht möglich, besser aber wäre es, das selbst herauszubekommen.
Das lässt sich natürlich rekursiv elegant lösen, oder aber (äquivalent) durch eine Schleife von i = 0 bis 2^n-1 (Bit j nicht gesetzt: Rechnung j wird nicht zur Gesamtsumme addiert, Bit j gesetzt: Rechnung j wird zur Gesamtsumme addiert), aber die Laufzeit macht das natürlich unrealistisch.
Eine Möglichkeit, sich dem zu nähern, ist von einer (1) fehlenden Rechnung auszugehen, dann muss man nur n Summen bilden und sehen, ob sich y ergibt. Wenn nicht, versucht man’s mit 2 fehlenden Rechnungen und n² Summen, 3 fehlenden Rechnungen und n³ Summen usw. Auch hier wird die Laufzeit schnell unrealistisch.
Frage also: Gibt es einen anderen Ansatz dafür?