Einfaches Problem...finde aber keinen Algorithmus dafür :(

Hi, habe ein einfaches Problem..finde aber keinen Algorithmus, welcher für große Werte auch noch recht schnell erfolgreich ist *heul

Problem:

Ich habe eine bestimmte Länge x. Nun habe ich 6 verschieden lange Gegenstände.
Ich muss nun die geringste Mögliche Anzahl an Gegenständen finden, welche
die Länge ausfüllen. Bei der Aneinanderreihung der Gegenstände ist zu beachten,
das Diese sich mindestens zu einem Wert MIN überlappen müssen und maximal zu einem Wert MAX überlappen dürfen. Auch muss die Länge x nicht vollständig ausgefüllt werden, sondern es kann bis zum maximalen Wert y Platz frei bleiben aber nicht mehr! Das sieht auf den ersten Blick einfach aus, aber ich komme auf keinen SCHNELLEN Algorithmus.

Ich habe folgende Lösung verwendet:

Zuerst habe ich rekursiv alle Möglichen Kombinationen ausgerechnet , welche in die Länge passen oder auch etwas überlappen. Alle Kombinationen werden in eine Liste gespeichert. Danach habe ich die Liste nach den oben genannten Restriktionen ausgewertet. Das Problem ist, das die Liste schon bei etwas größeren Werten für x mehrere Millionen Einträge umfasst. So dauert die Auswertung und Erstellung der Liste mehrere Stunden. Ich muss einen anderen Grundansatz finden. Vielleicht könnt Ihr mir dabei helfen das Problem zu lösen.
Habe schon nach dem "Rucksackproblem" geschaut, nur ist bei mir das Problem, dass sich die Gegenstände überlappen müssen und die Überlappung kann variabel
bis MAX sein. So hätte ich Praktisch das Rucksackproblem mit Gegenständen, welche sich zum Teil Variabel bis MAX verkleinern können ?!

Hier mein Algorithmus zur Erstellung der Liste (Pseudocode!)
(Wenn doch nur der wenigstens etwas schneller wäre)

Aufruf: calcCandidats(3000, 0)

Public Sub calcCandidats(länge As Double, vorherigeLänge As Double)
    Dim i As Double            'Zähler
    Dim l As Double            'Länge der Kombination an Gegenständen
    Dim Überlapp As Double     'Überlappung

    For i = 0 To 5
        l = LängeGegenstand(i) + vorherigeLänge

        If (l < länge) Then
            Call calcCandidats(länge, l)
            bigListe(bigIndex) = speichere l
            bigIndex = bigIndex + 1
        Else
            Überlapp = l - länge  'Überlappung berechnen
            l = l - Überlapp      'l auf Länge setzen  
            bigListe(bigIndex) = speichere l und Überlapp
            bigIndex = bigIndex + 1
        End If
    Next i
End Sub

Gruss

Finalbrain

RED-BARON

hallo,

Du hast wohl nicht ganz alles gelesen zum Rucksackproblem:

http://www.tinohempel.de/info/info/ti/rucksackproblem.htm

Deine Aufgabe ist es ja auch nicht die Kombination zu finden, bei der der Rucksack möglichst voll ausgenutzt wird.

Du schreibst:
Ich muss nun die geringste Mögliche Anzahl an Gegenständen finden, welche
die Länge ausfüllen.

Ich würde mal von allen Längen die MIN Überlappung subtrahieren um die maximale effektive der Längen zu bekommen.

Dann ist wohl mit der größten effektiven Länge zu beginnen, ( übersteigt diese die Gesammtlänge ist bei der nächst kleineren Länge zu beginnen )

Dann werden jeweils die nächst kleineren Längen addiert und geprüft ob diese
noch in die Gesammtlänge passen, evtl. die Überlappung vergrößern auf MAX Überlappung und erneut testen.

Liegt der erste Test zwischen MAX und MAX-y ist die Kombination gefunden.
Liegt der erste Test über MAX und der zweite Test unter MAX-y oder zwischen MAX und MAX-y ist die Kombination auch gefunden.

Sollte ich was übersehen oder Bedingungen Mißachtet haben, korrigiere mich bitte. Bei solchen Sachen macht es sich immer Gut das ganze mal mit Streichhölzern und ohne Rechner zu probieren ...

"Von der Lösung keine Spur, schaff Dir eine Hilfsfigur."

mfg
RB

dali

"Von der Lösung keine Spur, schaff Dir eine Hilfsfigur."

Lol

RED-BARON

hallo,

das sagte mal ein Lehrer immer, wenn keiner was kapierte und er am Verzweifeln
war oder er eine besonders leichte Aufgabe hatte war das der erste Satz.

Nach dem alle auf die Hilffigur konzentiert waren, und diese in Gestalt und Sinn derart verfremdet und vervielfältigt hatten, daß ein ganzes Comic gefüllt werden konnte war die Stunde rum und die Aufgabe auch nicht gelöst.

Der andere Ansatz war Geld zu sammeln und die Stunde mit Zisch und Flopp zu beginnen. Bei einer Flasche Bier ist die Horde halt ruhig zu halten und Automatengraphen werden plötzlich interessanter als man denken könnte.

Ewige Studenten besonders in Form und Gestalt eines Lehrkörpers sind halt doch
nicht ganz zu verachten.

mfg
RB