Beste Kombination zur Auffüllung einer Liste

[Valle]

Hi DPler, :hi:

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

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. :thumb:

Liebe Grüße,
Valentin

[gammatester]

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

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.

[Valle]

Zitat:

Zitat von gammatester (Beitrag 1220592)

Das ist ein überbestimmtes lineares Gleichungsytem.

Das klingt klasse! :-) Vielen Dank, damit kann ich denke ich arbeiten! :thumb:

Zitat:

Zitat von gammatester (Beitrag 1220592)

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:

Zitat von gammatester (Beitrag 1220592)

Einen Algorithmus kann ich allerdings nicht anbieten.

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

Liebe Grüße,
Valentin

[Volker Z.]

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:

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ß

[Valle]

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

[gammatester]

Zitat:

Zitat von Volker Z. (Beitrag 1220610)

(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...

[Volker Z.]

Hallo,

Zitat:

Zitat von gammatester (Beitrag 1220618)

Zitat:

Zitat von Volker Z. (Beitrag 1220610)

(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ß

[Uwe Raabe]

Die Aufgabestellung hat gewisse Ähnlichkeiten mit dem Rucksack-Problem, bei dem möglichst viele Dinge in den Rucksack gepackt werden sollen ohne ihn zu überfüllen. Die Unterschiede sind

a) die Dinge (Listen) sind in beliebiger Anzahl verfügbar
b) der Rucksack soll ganz voll sein

In diesem Fall bietet sich eine kombinatorische Lösung an. Dabei wird eine Liste in den Rucksack aufgenommen und der daraus resultierende Status überprüft. Ist der Rucksack noch nicht voll, mache ich einfach so weiter. Andernfalls habe ich entweder eine Lösung gefunden (Rucksack ist genau voll) oder der Rucksack ist überfüllt. In beiden Fällen muss ich die zuletzt eingepackte Liste wieder herausnehmen und nehme mir die nächste Liste. Bin ich nun bei der letzten Liste angekommen, nehme ich alle Vorkommen dieser letzten Liste raus. die dann "oberste" Liste nehme ich auch heraus und verfahre so, als ob der Rucksack voll gewesen wäre. Das ganze Spiel geht solange weiter bis ich nur noch Elemente der letzten Liste im Rucksack habe.

Konkret anhand der Beispieldaten:

L0 = [3, 2, 0]
L1 = [0, 0, 2]
L2 = [0, 0, 1]
L3 = [4, 0, 0]

Lösungsbedingung: [3, 2, 4]

Anfangszustand Rucksack: ()|[0,0,0] { leer }

1. (L0) [3,2,0]
2. (2*L0) [6,4,0] // überfüllt
3. (L0+L1) [3,2,2]
4. (L0+2*L1) [3,2,4] // Lösung
5. (L0+L1+L2) [3,2,3]
6. (L0+L1+2*L2) [3,2,4] // Lösung
7. (L0+L1+L3) [7,2,0] // überfüllt, L3 ist letzte Liste
8. (L0+L2) [3,2,1]
9. (L0+2*L2) [3,2,2]
10. (L0+3*L2) [3,2,3]
11. (L0+4*L2) [3,2,4] // Lösung
12. (L0+3*L2+L3) [7,2,3] // überfüllt, L3 ist letzte Liste
13. (L0+2*L2+L3) [7,2,2] // überfüllt, L3 ist letzte Liste
14. (L0+L2+L3) [7,2,1] // überfüllt, L3 ist letzte Liste
15. (L1) [0,0,2]
16. (2*L1) [0,0,4]
17. (3*L1) [0,0,6] // überfüllt
18. (2*L1+L2) [0,0,5] // überfüllt
19. (L1+L2) [0,0,3]
20. (L1+2*L2) [0,0,4]
21. (L1+3*L2) [0,0,5] // überfüllt
22. (L1+2*L2+L3) [4,0,4] // überfüllt, L3 ist letzte Liste
23. (L1+L2+L3) [4,0,3] // überfüllt, L3 ist letzte Liste
24. (L2) [0,0,1]
25. (2*L2) [0,0,2]
26. (3*L2) [0,0,3]
27. (4*L2) [0,0,4]
28. (5*L2) [0,0,5] // überfüllt
29. (4*L2+L3) [4,0,4] // überfüllt, L3 ist letzte Liste
30. (3*L2+L3) [4,0,3] // überfüllt, L3 ist letzte Liste
31. (2*L2+L3) [4,0,2] // überfüllt, L3 ist letzte Liste
32. (L2+L3) [4,0,1] // überfüllt, L3 ist letzte Liste
33. (L3) [4,0,0] // überfüllt, L3 ist letzte Liste, Ende der Kombinationen

Man kann das noch optimieren, in dem man alle Listen gleich raus wirft, die schon alleine zu einer Überfüllung führen. Dann spart man sich einen Haufen Iterationen.

[BUG]

Das Ganze ist ein (leider ganzzahliges) lineares Optimierungsproblem:
Dass die Kombinationen der Listeninhalte die Zielliste ergeben sollen, entspricht den Nebenbedingungen.
Die Zielfunktion ist der Preis einer solchen Kombination.

Meine erste Herangehensweise wäre eine naive Version des Branch-and-Bound-Verfahren:
Du machst eine Tiefensuche und jede gefundene gültige Kombination ist deine neue obere Preisschranke (wenn besser).
Die Suchstrategie ist vermutlich etwas, wo am einfachsten etwas optimiert werden könnte (siehe Uwe Raabe).
Im Moment fällt mir wenig ein, wie man sinnvoll eine untere Schranke nutzen könnte, aber vielleicht findest du eine gute obere Schranke mit irgendeiner Heuristik.
Außerdem kann man vermutlich eine untere Schranke für den Preis finden, den man von einer unvollständigen Lösung zu einer gültigen braucht. Damit könntest du mit deiner oberen Schranke mehr Branches abschneiden.

Du könntest das Problem aber auch mit jeder beliebigen Lösungsmethode für ganzzahlige lineare Programmierung lösen.

EDIT/OT:
Ich würde gerne mehr zu dem Problem erfahren ... also:
Was wird da modelliert, wie groß sind die Listen und wie viele sind es?
Außerdem wäre es schön, wenn du die Lösung skizzieren würdest, die du dann letztendlich umgesetzt hast.
Es ist interessant zu sehen, wie solche Probleme in der echten Welt gelöst werden.

[Valle]

Hi, :hi:

@Uwe: Vielen Dank für deine Antwort. Dein Post hilft mir wirklich weiter. Ich versuche gerade, deine Schritte in einen Algorithmus umzusetzen. Allerdings fällt mir dabei auf, dass ich die Regeln in denen du diese Listen durchgehst nicht zu verstehen scheine. Möglicherweise hat sich dort aber auch ein Fehler eingeschlichen. Beispielsweise wird die Kombination L1+L3 gar nicht ausprobiert? Hat das einen algorithmischen Grund, den ich nicht erkenne, oder fehlt einfach was?

@BUG: Sehr interessante Artikel, die ich mir sicher noch genauer anschauen werde. Auf den ersten Blick scheinen die Artikel komplizierter als das Problem selbst zu sein. Da werde ich wohl einfach noch ein paar Semester warten, dann kommt das bestimmt auch im Studium. ;-)

Du bekommst gern mehr Details zum Problem, sobald ich es gelöst habe. :P

Liebe Grüße,
Valentin

[Uwe Raabe]

Da hast du natürlich recht: es fehlen einige Kombinationen. Ich habe da wohl die Iterationen mit und ohne L3 (weil L3 ja eh nicht geht) vermischt. (L0+L3) wäre dann bei 14a und (L1+L3) bei 23a einzusortieren.

Für einen Algorithmus bietet sich ein rekursiver Ansatz an. Später kann man den ja immer noch serialisieren.

Als Datenstruktur für eine Lösung wäre ein array of Integer gut geeignet, in dem die Anzahl der einzelnen Listen vermerkt ist. Ich hab da mal quick and dirty was zusammengeschrieben, das du vielleicht als Basis nehmen kannst. Insbesondere die statischen Arrays wird man wohl durch dynamische ersetzen müssen.

Delphi-Quellcode:

program Project255;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils,
  System.Math;

type
  TSolution = array[0..3] of Integer;
  TListe = array[0..2] of Integer;

const
  Soll: TListe = (3,2,4);
  Listen: array[0..3] of TListe
       = ((3,2,0), (0,0,2), (0,0,1), (4,0,0));
  Kosten: array[0..3] of Integer = (10, 5, 4, 10);

function CalcKosten(const Solution: TSolution): Integer;
var
  I: Integer;
begin
  Result := 0;
  for I := 0 to 3 do
    Result := Result + Solution[I] * Kosten[I];
end;

procedure WriteIteration(const Solution: TSolution; const Liste: TListe; res: Integer);
var
  I: Integer;
  S: string;
begin
  S := '(';
  for I := 0 to 3 do
    S := S + IntToStr(Solution[I]) + ',';
  S[Length(S)] := ')';
  S := S + '[';
  for I := 0 to 2 do
    S := S + IntToStr(Liste[I]) + ',';
  S[Length(S)] := ']';
  if res = 0 then begin
    S := S + ' Lösung: ' + IntToStr(CalcKosten(Solution));
  end
  else if res > 0 then begin
    S := S + ' überfüllt';
  end;
  Writeln(S);
end;

procedure Iteration(var Solution: TSolution; const Liste: TListe; Index: Integer);
var
  newListe: TListe;
  I: Integer;
  newRes: Integer;
  res: Integer;
begin
  Inc(Solution[Index]);
  for I := 0 to 2 do
    newListe[I] := Liste[I] + Listen[Index, I];
  res := 0;
  for I := 0 to 2 do begin
    newRes := CompareValue(newListe[I], Soll[I]);
    if res <> newRes then begin
      if res = 0 then
        res := newRes
      else if newRes > 0 then
        res := newRes;
    end;
  end;
  WriteIteration(Solution, newListe, res);
  if res < 0 then begin
    Iteration(Solution, newListe, Index);
  end;
  Dec(Solution[Index]);
  if Index < 3 then begin
    Iteration(Solution, Liste, Index + 1);
  end;
end;

procedure Main;
var
  Solution: TSolution;
  Liste: TListe;
  I: Integer;
begin
  for I := 0 to 3 do
    Solution[I] := 0;
  for I := 0 to 2 do
    Liste[I] := 0;
  Iteration(Solution, Liste, 0);
end;

begin
  try
    Main;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  Readln;
end.

[Valle]

Coool, danke! :thumb:

Mein Ansatz war auch ein rekursiver, er funktioniert auch, hat allerdings viele Lösungen mehrfach gefunden...

Hier dein Code nach Anpassungen, Vereinfachungen und "Pythonifizierung":

Code:

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

soll = [3, 2, 4]
listen = [
        [3, 2, 0],
        [0, 0, 2],
        [0, 0, 1],
        [4, 0, 0],
]
kosten = [10, 5, 4, 10]

def CalcKosten(solution):
        return sum(s * k for s, k in zip(solution, kosten))

def CompareLists(a, b):
        """
        Gibt 0 zurück, wenn beide Listen gleich sind.
        Gibt 1 zurück, wenn wenigstens ein Element in a größer ist.
        Gibt -1 zurück, wenn wenigstens ein Element in a kleiner, aber keins größer ist.
        """
        if all([i == j for i, j in zip(a, b)]):
                return 0
        elif any([i > j for i, j in zip(a, b)]):
                return 1
        return -1

def Iteration(solution, liste, index=0):
        solution[index] += 1
        newListe = [j + k for j, k in zip(liste, listen[index])]
        res = CompareLists(newListe, soll)
        if res == 0:
                print('Lösung: %s, %i' % (solution, CalcKosten(solution)))
        if res == -1:
                Iteration(solution, newListe, index)
        solution[index] -= 1
        if index < len(listen)-1:
                Iteration(solution, liste, index + 1)

def main():
        solution = [0] * len(listen)
        liste = [0] * len(soll)
        Iteration(solution, liste);

if __name__ == '__main__':
        main()

@BUG: Also. ^^ Es geht um Buchungen einer Ferienwohnung. Diese Buchung kann mit Aufbettungen ausgestattet werden. Eine Aufbettung entspricht nicht nur einfach einem Bett, sondern einer Art 3er Tupel: (Anzahl Erwachsenenbetten, Anzahl Kinderbetten, Anzahl Babybetten). Für jede Ferienwohnung gibt es eine ganze Menge solcher Aufbettungsmöglichkeiten. Das liegt daran, dass es einzelne oder zB. doppelstöckige Betten gibt (Doppelstockbett = (0, 2, 0)). Außerdem können teilweise auch kleinere Häuser ("Studios") aufgeschlossen werden, die erneut Betten bieten.

Gegeben habe ich also ein Tupel an notwendigen Aufbettungen. Also eine Differenz aus Inklusivbetten und tatsächlichen Teilnehmern der Buchung. Und gesucht ist die billigste Kombination aus Aufbettungsoptionen, die genau die notwendige Bettenzahl abdeckt.

Sicher hätte man das Problem auch anders lösen können. Aber das war meine erste Idee. Und die hat mich so sehr fasziniert, dass ich jetzt auch wissen wollte, wie man es allgemein löst.

Vielen Dank euch allen. :-)

Liebe Grüße,
Valentin

[BUG]

Jetzt wo ich deine Lösung so sehe: Vermutlich könnte man auch was mit dynamische Programmierung erreichen.
Gerade, wenn die Sollwerte klein und die Anzahl der möglichen Kombinationen groß ist, sollte das etwas bringen.

Das könnte so aussehen: Für jeden Aufbettungswert kleiner des Soll-Werts wird nur die beste Zusammenstellung aus den Listen gespeichert. In jeder Iteration wird ein Element aus den Restlisten genommen und mit allen möglichen/sinnvollen Faktoren auf die aktuelle Zusammenstellung addiert. Ungültige Zwischenergebnisse werden weggeschmissen und alle optimalen Zwischenergebnisse für die nächste Iteration aufgehoben.

Das Interessante an dieser Lösung: Du braucht nur Anzahl der Listen viele Iterationen und die Liste der optimalen Zwischenergebnisse wird für ein Soll-Wert von [n, m, k] höchstens (n+1)*(m+1)*(k+1) groß :)

Zitat:

Zitat von Valle (Beitrag 1220751)

Und gesucht ist die billigste Kombination aus Aufbettungsoptionen, die genau die notwendige Bettenzahl abdeckt.

Das finde ich eine etwas merkwürdige Einschränkung. Mehr Betten sollten doch auch OK sein :gruebel:
Aber ist vermutlich nicht von dir beeinflussbar :mrgreen:


EDIT/OT:

Zitat:

Zitat von Valle (Beitrag 1220723)

Da werde ich wohl einfach noch ein paar Semester warten, dann kommt das bestimmt auch im Studium. ;-)

So als Tipp, wenn du die Wahl hast: Theoretische Informatik und (algorithmische) Graphentheorie sind imho ziemlich interessant für Informatiker, die sich für Algorithmen interessieren, die über das Sortieren von Listen hinaus gehen :wink: Wenn du mal in der DP herum guckst, findest du unter den schwierigeren Themen jede Menge Optimierungsprobleme und Sachen, die sich durch Graphen modellieren lassen. Abgesehen von den typischen kombinatorischen Problemen, die auch von der theoretischen Informatik behandelt werden.