Hi DPler,

ich hab hier ein algorithmisches Problem. Vorschläge zur Verbesserung des Thread-Titels sind aber auch willkommen.

Gegeben ist eine Liste, die zum Beispiel so aussieht:

markieren

Code:

[3, 2, 4]

Außerdem ist eine Liste solcher Listen gegeben, zum Beispiel so:

markieren

Code:

[3, 2, 0], Kosten 10
[0, 0, 2], Kosten 5
[0, 0, 1], Kosten 4
[4, 0, 0], Kosten 10

Zu jeder dieser Listen aus der letzten Liste existiert eine Art Kosten-Feld. Gesucht sind diejenigen Kombination aus Listen, die aufsummiert die erste Liste ergibt. Davon suche ich dann außerdem die billigste. Die zwei möglichen Kombinationen in meinem Beispiel wären dann übrigens:

markieren

Code:

[3, 2, 0] + 2 * [0, 0, 2]

und

markieren

Code:

[3, 2, 0] + 4 * [0, 0, 1]

. Die erste Kombination hätte Kosten von 20, die letzte würde 26 kosten. Die erste Kombination ist damit die gesuchte Lösung. (Edit:// Ich sehe gerade dass es noch eine eine weitere mögliche Lösung gibt. Sie ist aber auch nicht billiger und das Beispiel sollte klar sein.)

Mir fehlt da leider schon der Ansatz um auf die möglichen Kombinationen zu kommen. Herausfinden, welches die billigste Alternative ist, kann man ja anschließend nach der Betrachtung aller Möglichkeiten.

Hat jemand einen Tipp? Gibt es dazu ein bekanntes Problem o.ä.? Ich brauche keine fertige Lösung. Nur ein Schubser wäre toll.

Liebe Grüße,
Valentin

Nur ein paar Hinweise/Überlegungen: Du suchst doch wahrscheinlich positive ganze Zahlen a,b,c,d mit

markieren

Code:

a*[3, 2, 0] + b*[0, 0, 2] + c*[0, 0, 1] + d*[4, 0, 0] = [3, 2, 4]

Das ist ein überbestimmtes lineares Gleichungsytem. Wenn es überhaupt Lösungen gibt (wie man leicht sieht, gibt es bei Dir keine, wenn statt [3, 2, 4] zb [5, 2, 4] das Ziel wäre, weil 3a+4d = 5 nicht lösbar ist), kannst Du die Kosten errechnen. Ein weiteres Problem sind dann nur noch verschiedene Lösungen mit gleichen Kosten.

Einen Algorithmus kann ich allerdings nicht anbieten.

Zitat von gammatester:

Das ist ein überbestimmtes lineares Gleichungsytem.

Das klingt klasse! Vielen Dank, damit kann ich denke ich arbeiten!

Zitat von gammatester:

Problem sind dann nur noch verschiedene Lösungen mit gleichen Kosten.

Das wird in der Realität vermutlich nicht vorkommen. Falls doch hätte es für meine Anwendung dann keine Relevanz, welche Lösung genommen würde.

Zitat von gammatester:

Einen Algorithmus kann ich allerdings nicht anbieten.

Will ich auch gar nicht. Selbst denken macht mehr Spaß.

Liebe Grüße,
Valentin

Hallo,

die vorgeschlagene Lösung ist nicht zielführend. Wenn Deine Listen - wie im Beispiel - 3elementig sind und Du das vorgeschlagene lineare Gleichungssystem mit mehr als drei Vektoren (Listen) - die alle ungleich (0, 0, 0) sind - lösen möchtest, dann wirst Du eine unendliche Anzahl an Lösungen erhalten (vier oder mehr Vektoren aus dem R3 sind immer linear abhängig).

Die Aussage

Zitat:

[...] (wie man leicht sieht, gibt es bei Dir keine, wenn statt [3, 2, 4] zb [5, 2, 4] das Ziel wäre, weil 3a+4d = 5 nicht lösbar ist) [...]

ist falsch. (3, 2, 0) + 2 * (0, 0, 2) + 0 * (0, 0, 1) + 0,5 * (4, 0 , 0) = (5, 2, 4)

Du musst schon alle möglichen Listenkombinationen suchen. Soll heißen: Suche Lösungen für die Gleichungssysteme A1x = b, A2x = b, ..., Anx = b. Für alle Ai, für die eine Lösung existiert dann die Kosten berechnen.

Wenn die Listen 3elementig sind könntest Du die Determinante berechnen. Ist die Null gibt es keine Lösung. Wenn:

markieren

Code:

    (a11 a12 a13)
A = (a21 a22 a23), dann Det (A) = a11a22a33 -a11a23a32 - a12a21a33 + a12a23a31 + a13a21a32 - a13a22a31
    (a31 a32 a33)

Sorry, leider kann ich die Indizes nicht tiefstellen.

Gruß

Hallo Volker,

ich habe jetzt 'ne ganze Weile versucht mit der Lösung weiter zu kommen, konnte damit aber höchstens das Problem in kleinere Probleme zerschlagen, die ich zwar alle lösen könnte, allerdings alles nicht schön.

Problem scheint zu sein, dass es sich nicht um ein überbestimmtes, sondern um ein unterbestimmtes Gleichungssystem handelt. Das algorithmisch zu lösen ist nicht mehr ganz so einfach.

gammatester hat schon Recht mit seiner Aussage, dass es für die 5 keine Lösung gibt. Denn er schrieb vorher, dass nur ganzzahlig positive Multiplikatoren erlaubt sind. Unter dieser Vorraussetzung gibt es eine endliche Anzahl an Lösungen. Allerdings hilft mir das leider doch nicht so viel weiter wie erhofft.

Liebe Grüße,
Valentin

Zitat von Volker Z.:

(3, 2, 0) + 2 * (0, 0, 2) + 0 * (0, 0, 1) + 0,5 * (4, 0 , 0) = (5, 2, 4)

Also für mich ist 0.5 keine ganze Zahl, aber wenn Du meinst...

Hallo,

Zitat von gammatester:

Zitat von Volker Z.:

(3, 2, 0) + 2 * (0, 0, 2) + 0 * (0, 0, 1) + 0,5 * (4, 0 , 0) = (5, 2, 4)

Also für mich ist 0.5 keine ganze Zahl, aber wenn Du meinst...

Sorry, habe Deine Nebenbedingung überlesen.

Gruß