4. Suche nach Algorithmus

Suche nach Algorithmus

  • G

    Hallo,

    ich bin auf der Suche nach nem Algorithmus...
    Und zwar geht es darum, aus ner Menge von Zahlen beliebig viele Zahlen so auszuwählen, dass ihre Summe möglichst nah an einer anderen Zahl liegt.

    Beispiel:
    M = {2;5;7;8;13}
    Für n = 19 wäre 13+5=18 die Lösung.

    Ich hoffe ihr versteht was ich meine 🙂

    MfG Mathias

    0
  • ?

    Hi

    Ich formalisiere das mal.

    Gegeben:
    S={x_1,...,x_n},x_i∈N_+,t∈N+S = \{x\_1,...,x\_n\}, x\_i \in N\_+, t \in N_+

    Entscheidungsproblem:
    Gibt es ein
    S′⊂SS' \subset S
    derart, dass
    ∑x_i∈S′x_i=t\sum_{x\_i \in S' } x\_i = t

    Optimierungsproblem:
    Gesucht ist
    S′⊂SS' \subset S
    derart, dass
    ∑x_i∈S′x_i=maximal\sum_{x\_i \in S'} x\_i = maximal
    ∑x_i∈S′x_i≤t\sum_{x\_i \in S'} x\_i \leq t

    Das Entscheidungsproblem ist NP-Vollständig.
    D.h. grob gesagt, dass kein effizienter Algorithmus bekannt ist um dieses Problem zu lösen. Gleiches gilt für das Optimierungsproblem was genau deiner Aufgabe entspricht.

    D.h. du kannst dir selbst einen Algorithmus schreiben, der alle Teilmengen durchprobiert. Der wird exponentielle Laufzeit haben und nur für kleine Mengen verwendbar sein aber etwas wesentlich besseres gibt es einfach nicht.

    Alternativ gibt es für das Untermengen-Summen-Problem aber auch Approximations-Algorithmen die vielleicht für deine Zwecke reichen könnten.

    Google sollte dazu mehr wissen.

    Gruß, space

    0
  • G

    Schade dass es dafür keine Lösung gibt.

    Teilmengen durchprobieren ist da ja der erste Gedanke, aber wie schon gesagt zu aufwändig.

    0
  • W

    space schrieb:

    Ich formalisiere das mal.

    Gegeben:
    S={x_1,...,x_n},x_i∈N_+,t∈N+S = \{x\_1,...,x\_n\}, x\_i \in N\_+, t \in N_+

    Entscheidungsproblem:
    Gibt es ein
    S′⊂SS' \subset S
    derart, dass
    ∑x_i∈S′x_i=t\sum_{x\_i \in S' } x\_i = t

    Optimierungsproblem:
    Gesucht ist
    S′⊂SS' \subset S
    derart, dass
    ∑x_i∈S′x_i=maximal\sum_{x\_i \in S'} x\_i = maximal
    ∑x_i∈S′x_i≤t\sum_{x\_i \in S'} x\_i \leq t

    Falsch formalisiert! Das war nicht die Aufgabe.

    0
  • ?

    Wie ich solch klugscheißerische Ausrufe ohne Begründung hasse.
    Hässliche Marotte die sich da in Foren entwickelt...

    Dann ersetz eben die zweite Bedinung im Optimierungsproblem durch
    ∥∑x_i∈S′x_i−t∥=min\| \sum_{x\_i \in S'} x\_i - t \|= min

    Weniger NP-Vollständig wirds dadurch wohl nicht.

    EDIT:
    Hab grad bemerkt, dass dann die Maximierung keinen Sinn mehr macht.
    Also entweder die beiden obigen Bedingungen oder die Umkehrung. D.h. Summe minimieren und von unten mit t beschränken.

    0
  • W

    space schrieb:

    Wie ich solch klugscheißerische Ausrufe ohne Begründung hasse.
    Hässliche Marotte die sich da in Foren entwickelt...

    So ärgert sich der, der auf einen Fehler aufmerksam gemacht wurde. 😉

    space schrieb:

    Dann ersetz eben die zweite Bedinung im Optimierungsproblem durch
    ∥∑x_i∈S′x_i−t∥=min\| \sum_{x\_i \in S'} x\_i - t \|= min

    Dein EDIT hab ich nicht verstanden, aber das hier ist genau das richtige. Aber ein ∣⋅∣|\cdot | hätte doch auch gereicht, nicht wahr?

    space schrieb:

    Weniger NP-Vollständig wirds dadurch wohl nicht.

    Ist mir völlig egal.

    0
Anmelden zum Antworten