Benjamin: Kombinatorik / Variationen / Kombinationen

SELF-Forum

Kombinatorik / Variationen / Kombinationen

Benjamin
– Informationen zu den Bewertungsregeln

Hallo,

ich möchte mittels php folgende Problematik lösen:

Ich habe eine Zahlenmenge, die aus etwa 20 - 40 Zahlen besteht.
Nun möchte ich eine (unbekannte) Teilmenge dieser Zahlen so aufaddieren lassen, daß ich eine vorgegebene "Zielsumme" erreiche.
Das Programm soll mir die dabei genauen Kombinationen ermitteln, die mich zu der gewünschten Zielsumme führen.

einfaches Beispiel:

Zahlenmenge: 2, 4, 6, 8, 12
Zielsumme: 20
Kombinationen:
(1) 2, 4, 6, 8 = 20
(2) 2, 6, 12 = 20
(3) 8, 12 = 20

Kann mir jemand einen Tip für einen Ansatz zur Problemlösung geben?
Ich dachte an die Verwendung von Arrays und mehreren verschachtelten Schleifen.
Vorab vielen Dank und viele Grüße

Benjamin

Beitrag melden
–
Informationen zu den Bewertungsregeln

  1. Kombinatorik / Variationen / Kombinationen

    Gunnar Bittersmann Homepage des Autors
    – Informationen zu den Bewertungsregeln

    @@Benjamin:

    Kann mir jemand einen Tip für einen Ansatz zur Problemlösung geben?

    Rucksackproblem > SUBSET-SUM

    Live long and prosper,
    Gunnar

    --
    „Das Internet ist ein großer Misthaufen, in dem man allerdings auch kleine Schätze und Perlen finden kann.“ (Joseph Weizenbaum)
    Beitrag melden
    –
    Informationen zu den Bewertungsregeln

    1. Kombinatorik / Variationen / Kombinationen

      Benjamin
      – Informationen zu den Bewertungsregeln

      Vielen Dank, Gunnar.
      Die Subset-Sum ist genau der Ansatz, den ich brauche. Nun werde ich sehen, inwieweit ich das in ein Programm "verwandeln" kann.

      Viele Grüße
      Benjamin

      Beitrag melden
      –
      Informationen zu den Bewertungsregeln