Hallo zusammen
Ich habe da eine mathematische Frage zur "Mengenlehre".
Ich habe eine Liste mit verschiedenen werten (int) nun möchte ich anhand einer bestimmten Summe die passenden Werte finden.
Zb. :Summe y ist 60
Werte in der Liste
30
20
5
10
15
17
3
Das Ergebnis sollte sein:
30, 20, 10
30, 10, 17, 3
20, 5, 15, 17, 3
30, 5, 15, 10 usw.
Kann mir da jemand weiterhelfen.
Riecht nach Rucksackproblem.
Was hast du bisher versucht?
- performance is a feature -
Microsoft MVP - @Website - @AzureStuttgart - github.com/BenjaminAbt - Sustainable Code
Rucksack hat nochmal einen weiteren Wertebereich den man abgleichen muss.
Wie viele Zahlen sind es? Der einfachste Ansatz für das jetzige Problem ist, jede Zahl entweder zu wählen oder nicht zu wählen und dann zu prüfen ob die Summe erreicht ist.
Wenn es um viele Zahlen geht kann das länger dauern, dann müsste etwas mehr Strategie dazu kommen.
In Algorithm to determine which numbers in a list are the sum of a given number sowie Finding all possible combinations of numbers to reach a given sum gibt es einige Codebeispiele.
PS: Wenn auch negative Zahlen in der Liste vorkommen, dann handelt es sich um das Teilsummenproblem (bzw. in englisch Subset sum problem).
Bei der gegebenen Liste und dem Endresultat kann man erkennen, dass einige Zahlenkombinationen nur gemeinsam auftreten, z.B. 17+3, 15+5... Damit könnte man den Rechenaufwand beim Iterieren auch etwas reduzieren.
Goalkicker.com // DNC Magazine for .NET Developers // .NET Blogs zum Folgen
Software is like cathedrals: first we build them, then we pray 😉