Beste Kombination zur Auffüllung einer Liste

[Valle]

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:

Code:

[3, 2, 4]

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

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:

Code:

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

und

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