Summe aus positiven und negativen Zahlen

07.11.2019, 10:46

Summe aus positiven und negativen Zahlen

Meine Frage:
Ich will aus einer Menge an Zahlen, die positiv und negativ sein können, welche Kombinationen der Zahlen die gewünschte Summe X ergibt.

z.B.
Menge{-4.02, 3, 8,14, 14,02, -1}
gesucht: 10
14.02 - 4.02 = 10
3 + 8 -1 = 10

Habt ihr eine Idee, wie man diese Aufgabenstellung am besten bewältigen kann?

Meine Ideen:
Für nur Positive oder nur negative hat es bereits funktioniert.
Jedoch wenn sich die Summe X aus pos und neg Zahlen zusammen setzt komme ich auf keine brauchbare lösung.

07.11.2019, 11:01

Steffen Bühler

Auf diesen Beitrag antworten »

RE: Summe aus positiven und negativen Zahlen
Willkommen im Matheboard!

Das ist ein Teilsummenproblem und nicht so einfach lösbar. Ich würde mir ein Programm schreiben.

Viele Grüße
Steffen

07.11.2019, 11:06

HAL 9000

Auf diesen Beitrag antworten »

Fragen der Effizienz außen vor gelassen kann man natürlich bei $\begin{eqnarray*} n \end{eqnarray*}$ Zahlen alle $\begin{eqnarray*} 2^n \end{eqnarray*}$ Teilmengen und deren Summen betrachten. Kommt jetzt also drauf an, wie groß dein $\begin{eqnarray*} n \end{eqnarray*}$ ist: Bei $\begin{eqnarray*} n\leq 20 \end{eqnarray*}$ kann man das mit Computerunterstützung noch locker bewältigen, weiter oben wird die Luft dann zunehmend dünner (jedes nächstgrößere $\begin{eqnarray*} n \end{eqnarray*}$ verdoppelt ungefähr die Rechenzeit).

Ansonsten: Mit $\begin{eqnarray*} \leq \end{eqnarray*}$ statt $\begin{eqnarray*} = \end{eqnarray*}$ wären wir beim Rucksackproblem, aber das war dir vermutlich schon bewusst.

Zitat:

Original von [email protected]
Für nur Positive oder nur negative hat es bereits funktioniert.

Ich seh jetzt nicht den prinzipiellen Unterschied mit Ausnahme dessen, dass man die Anzahl der zu untersuchenden Teilmengen da besser beschneiden kann. Vielleicht erläuterst du ja mal, wie du da vorgegangen bist.

Neue Frage »

Antworten »

Summe aus positiven und negativen Zahlen

Verwandte Themen