Algorithmus - Wie kann ich aus einen beliebig langen Array alle erdenklichen Summen bilden?

...komplette Frage anzeigen

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).

Was möchtest Du wissen?