Optimierungsproblem

M

MikeBi

Mitglied
Hallo,

ich habe da mal ein kleines Optimierungsproblem. Vielleicht hat schon jemand so etwas (oder ahnliches) gelöst. Gegeben ist eine Gesamtlänge. Diese soll in Abschnitte unterteilt werden. Die Abschnitte haben unterschiedliche, fest vorgegebene Längen. Gleiche Abschnitte (Längen) können mehrfach vorkommen. Ich möchte "eigentlich nur" so nah wie möglich an die Gesamtlänge kommen.
Vielen Dank.

Mike
 
Hallo,

ich denke du musst dein Problem noch ein wenig genauer erklären...
Du bekommst eine Liste mit vorgegebenen Längen. Musst du die alle verwenden, oder sollst du nur diejenige Kombination herausfinden, die deren zusammen gesetzte Länge möglichst nahe an der gegebenen Gesamtlänge liegt?

Gruß Tom
 
Ich muss nur die Kombination finden, die das beste Ergebnis bringt. Die Anzahl der einzelnen Abschnitte ist aber begrent. Konkret geht es um Werkzeuge für eine Maschine. Es ist nur eine begrenzte Anzahl von Werkzeugen vorhanden. Die restliche Länge soll mit einem Spalten ausgeglichen werden. Wobei natürlich der sich ergebende Spalt so klein wie möglich sein soll.

Mike
 
Also mal gaaanz einfach: Ich stelle mir das so vor, dass ich eine Kiste voll mit unterschiedlich langen Abschnitten habe, die hintereinandergelegt möglichst nahe an eine vorgegebene Gesamtlänge heranreichen müssen.

Dabei zu beachten ist:
1) Die Anzahl der Abschnitte die man verwenden darf ist begrenzt
2) Die Gesamtlänge der Abschnitte darf nur <= der Gesamtlänge sein.

Ist das so richtig? Wenn nicht... bitte um Korrektur, anschließend werde ich mal (sobald der Kaffee dann mal irgendwann wirkt) drüber nachdenken.
 
Hab für eine Plan Zahlungssoftware sowas ähnliches gemacht.

Ich würde einfach erstmal eine List erstellen mit allen Abschnitten. (Liste A)
Diese sortieren das der größte Abschnitt an erster Stelle ist.

Und dann eine neue Liste anlegen welche die gültigen Abschnitte hält. (Liste B)

Nun in einer Schleife (2 SChleifen, die erste die ein flag prüft und die innere Schleife die Liste A durschläuft) alle Abschnitte durchlaufen (Liste A), wenn akt. Abschnitt + Summe Liste B kleiner Gesamtlänge. Dann Abschnitt der Liste B hinzufügen.

Die Schleife mit dem flag wird erst beendet wenn kein Abschnitt mehr der Lsite B hinzugefügt werden konnte.

Ungefähr So:
Code: 
Liste A //alle Abschnitte
Liste B // gefundene Abschnitte
bool ende=false;
decimal gesamtlaenge;
decimal summe;

solange ende==false
{
    ende=true; //erstmal sagen schleife ist fertig
    foreach Akt.Abschnitt von Liste A
    {
         wenn Akt.Abschnitt + summe <= gesamtlaenge //trifft zu anfügen
         {
                  Liste B hinzufügen Akt.Abschnitt
                  ende=false //es wurde ein passendes Element gefunden, Schleife nochmal prüfen

                  summe += Akt.Abschnitt
         }
    }
}

Hoffe war verständlich
 
Mit diesem Ansatz habe ich das Problem zur Zeit gelöst. Leider findet die Routine nicht immer die optimale Lösung
z.B.
ges.:100 mm
geg 3 x 60 mm
2 x 30 mm
2 x 20 mm
Lösung der Routine 1 x 60 mm + 1 x 30 mm = 90 mm
besser 1 x 60 mm + 2 x 20 mm = 100 mm

Das ist jetzt nur ein kleines Beispiel gewesen.
 
Wieviel Wertegruppen können denn gegeben sein. In deinen Fall würde ich eine Schleife dreimal verschachteln und rekursiv aufrufen, bis ich am nächsten von gesamt dran bin.
Oder brauscht du mehrere Ergebnisse?
z.B.
ges.:100 mm
geg 3 x 60 mm
2 x 30 mm
2 x 20 mm
Ergebnis1: 1 x 60 mm + 2 x 20 mm = 100 mm
Ergebnis2: 2 x 30 mm + 2 x 20 mm = 100 mm
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück