Beste Kombination zur Auffüllung einer Liste

[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!

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 von Valle:

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
Aber ist vermutlich nicht von dir beeinflussbar


EDIT/OT:

Zitat von Valle:

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