Algorithmus zur Verfügbarkeitsberechnung

[jfheins]

Ich schlage mal "intelligentes Duchprobieren" vor.

Es gibt ja 2 Zustände, 0 und 1. Die Spaltensumme soll immer 1 ergeben, die Zeilensumme einen definierten Wert. Jetzt werden erstmal alle Summen gebildet. Dann wird geschaut, wo zuviel ist. (Klar soweit?) Dann jeweils die Zeile und die Spalte mit der größten Summe hernehmen und den Wert in der Zelle durch eine 0 ersetzen. Dann prüfen ob alle Bedingunen erfüllt wurden. Wenn nicht, den gleichen Algorithmus rekursiv anwenden, wenn das auch nicht hilft eine alternative Zelle auf 0 setzen.

Also eine (einfache) Heuristik und Backtracking. Könnte ganz gut funktionieren, und liefert garantiert ein Ergebnis wenn es eines gibt. Die Frage ist nur, wie lange es braucht - das kann ich jetzt nicht genau abschätzen. Für das Beispiel tippe ich mal auf eine Laufzeit unter 100ms.

[BUG]

Delphi-Quellcode:

function belegung(pcStunden: array[1..i] of Cardinal): array[1..j] of [0..i];
var
  aktPc: Cardinal;
  aktZeit: Cardinal;
begin
  // keine PCs zugeteilt
  for aktZeit := 1 to j do
    result[aktZeit] := 0;
  // nacheinander PCs durchgehen und Zeiten belegen
  aktZeit := 1;
  for aktPc := 1 to i do
  begin
    while pcStunden[aktPc] > 0 do
    begin
      if aktZeit > j then
        raise "Mehr PC-Stunden aus freie Zeiten";
      pcStunden[aktPc] := pcStunden[aktPc] - 1;
      result[aktZeit] := aktPc;
      aktZeit := aktZeit  + 1;
    end;
  end;
  if aktZeit <= j then
    raise "Weniger PC-Stunden als freie Zeiten";
end;

Das Ergebnis sieht dann so aus:

Code:

   |H1|H2|H3|H4|H5|H6|H7|H8|H9
PC1| 1| 1| 1| 0| 0| 0| 0| 0| 0
PC2| 0| 0| 0| 1| 1| 1| 0| 0| 0
PC3| 0| 0| 0| 0| 0| 0| 1| 1| 0
PC4| 0| 0| 0| 0| 0| 0| 0| 0| 1

Wieso möchtest du dieses Ergebnis nicht (ich nehme mal an du willst es nicht so)?

[jfheins]

Zitat von BUG:

Wieso möchtest du dieses Ergebnis nicht (ich nehme mal an du willst es nicht so)?

Also in dem Beispiel sind 2 "Matrizen" abgebildet, und zwar oben eine mit den Verfügbarkeiten. Und nur wo dort eine 1 steht, darf am Ende eine 1 stehen.

[jobo]

@Bug
Deine Lösung berücksichtigt nicht die >"Erreichbarkeit"

[BUG]

Zitat von jfheins:

Also in dem Beispiel sind 2 "Matrizen" abgebildet, und zwar oben eine mit den Verfügbarkeiten. Und nur wo dort eine 1 steht, darf am Ende eine 1 stehen.

Ich wusst doch, dass ich was übersehen habe