Summe aus elementen einer Liste

25.04.2006, 18:34	virtex	Auf diesen Beitrag antworten »
Summe aus elementen einer Liste Ich habe eine Liste von n-Zahlen: { x1, x2, x3, .., xn } sowie eine Zahl y. Ich versuche y durch eine Summe mehreren dieser Zahlen auszudruecken. d.h: z.B. y=100 Liste { 10, 10, 10, 20, 50, 50, 100, 200} y=100 y= 50+50 y= 50 + 20 + 10 + 10 + 10 usw.. Wie finde ich am schnellsten alle Loesungen?
25.04.2006, 18:39	Dual Space	Auf diesen Beitrag antworten »
Ehrlich gesagt, habe ich deine Frage/Aufgabe nicht so recht verstanden.
25.04.2006, 19:03	virtex	Auf diesen Beitrag antworten »
Also. Gegeben: Eine Liste x aus n Elementen [\{x_1,x_2,x_3,...x_n\}] und y $\begin{eqnarray} y=\sum_{k=1}^n~a_kx_k \end{eqnarray}$ aber $\begin{eqnarray} a_k \end{eqnarray}$ darf nur 0 oder 1 sein Gesucht: Alle Loesung fuer a d.h. Loesung 1: $\begin{eqnarray} a = \{ a_1, a_2, a_3,..,a_n \} \end{eqnarray}$ Loesung 2: $\begin{eqnarray} a = \{ a_1, a_2, a_3,..,a_n \} \end{eqnarray*}$ usw. Ich suche Loesungsansaetze/einen Algorithmus um alle Loesungen per Computer zu berechnen.
25.04.2006, 19:23	papahuhn	Auf diesen Beitrag antworten »
Das ist das Rucksackproblem. Schau mal, ob du bei Google einen Algorithmus dazu finden kannst.
25.04.2006, 19:25	Dual Space	Auf diesen Beitrag antworten »
Ahh ... habs verstanden. Ich würde es mit einem Backtrackingalgorithums implementieren. Höchst wahrscheinlich ist es das selbe was papahuhn auch meint.
25.04.2006, 19:27	papahuhn	Auf diesen Beitrag antworten »
Ich sehe gerade, dass das NP-vollständig ist. Dann kannste genausogut alle 0/1-Kombinationen durchprobieren.
Anzeige

25.04.2006, 20:07	virtex	Auf diesen Beitrag antworten »
Danke vielmal! Es ist ein Spezialfall des Rucksacksproblem (Subset sum).
25.04.2006, 21:32	virtex	Auf diesen Beitrag antworten »
Danke vielmal! Hab die Routine in meiner Applikation implementiert.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »