Algorithmus - Wie kann ich aus einen beliebig langen Array alle erdenklichen Summen bilden?
Hallo Zusammen :)
Ich habe vor kurzem eine interessante Aufgabe bekommen, bei der weder ich, noch der Aufgabensteller wissen ob und wie es möglich ist.
Problem ist Folgendes: Ich soll ein Programm schreiben, welches eine beliebige Anzahl von Doublewerten entgegennimmt und daraus alle nur möglichen summen bildet. Und mit allen Summen meine ich auch Summen aus beispielsweise 3,4,5 oder mehr Summanden.
Ich stehe momentan ziemlich auf den schlauch und ich habe auch noch keinen Algorithmus gefunden der mit der variablen Arraygröße mit skaliert.
Hoffe ich konnte mich verständlich ausdrücken. Ich bin echt für jede Hilfe dankbar! (Vorschläge wären mir am Liebsten in c# oder Java)
2 Antworten
Eine Lösung wäre wenn du einen Algorithmus implementierst der dir aus einem double-Array dessen Potenzmenge berechnet. Du hast dann sozusagen ein Array aus Arrays die alle möglichen Kombinationen von Summanden enthalten. Dann musst du dir nur noch die Arrays mit der Länge x raussuchen (für alle x-summandigen Summen) und jeweils aufaddieren.
Wenn du keine Lust hast dich mit der Arraygröße herumzuschlagen (um bei der Eingabe der Werte zu wissen wie groß du dein Array machen musst), nimm einfach statt einem double-Array die Klasse List<double> bzw. ArrayList<double> (in Java).
Code dazu findest du im Internet, falls du es nicht schaffst.
Natürlich benötigt diese Art von Aufgabe viel Speicher, vor allem diese Lösung wenn du erstmal die ganze Potenzmenge berechnest
Das ginge z.B. über einen dynamic programming Ansatz: https://en.wikipedia.org/wiki/Dynamic_programming. Dabei entsteht eine 2D-Tabelle mit allen möglichen Untersummen (die sicher einige Dopplungen enthält die man im Anschluss herausfiltern muss).