Optimale Länge berechnen

[eisdiele]

Hallo,

ich hab folgende vorgaben:

Minimallänge

Maximallänge

Teile bestimmter länge

Erreichen soll ich ein Wert, der der Minimallänge möglichst nahe kommtm, ich so wenig wie möglich Teile benutze und dabei die Teile möglichst kurz sind.

Hier mal paast beispiele zum besseren Verständnis:

Minimal 600

Maximal 1000

Teile: 100, 300, 300, 500

500 + 100 würde zwar passen (das findet mein Algorithmus)

aber

300 + 300 wäre besser.

Zur zeit läuft des so, dass ich das längste Teil nehm das ich hab und dann geschaut wird obs passt, wenn ja, wird das nächst längste genommen usw.

irgendwer ne idee wie ich des lösen könnte? Programmiersprache ist C++

[trebstyle]

seh ich das richtig, je geringer der unterschied zwischen den zwei teilen ist, desto günstiger das ergebnis ist?

[P3AC3MAK3R]

"Minimallänge" sollte doch eigentlich bedeuten, daß diese auch mindestens erreicht wird, oder ("möglichst nah kommen" ist ja etwas anderes)?

Müssen auch Konstellationen mit mehr als zwei Teilen berücksichtigt werden?

[eisdiele]

hmm, es geht erstmal darum, so wenig wie möglich teile zu verwenden. wenn man das dann hat, dann sollten die Stücke möglichst klein sein, das spielt aber nur ne untergeordnete rolle und ist quasi nur ne optimierung...

edit: Die Mindestlänge darf logischerweise überschritten werden (nur halt möglichst wenig, spart dann in weiteren schritten viel arbeit... ), sollte es aber anhand der Teile die man hat (was quasi beliebig viele sein können) nicht möglich sein, die Mindestlänge zu erreichen, muss versucht werden da möglichst nah ranzukommen.

ich probiers grad mit nem rekursiven suchverfahren, aber mir sagt des net sonderlich viel... ^^

[TDM]

Sind die Teile sortiert ?

Wenn ja, sollte man da aus der Mitte (der Liste) einfach einen nehmen und mit dem Vorgänger bzw. Nachfolger abgleichen.

[geloescht_Newlukai]

Zur zeit läuft des so, dass ich das längste Teil nehm das ich hab und dann geschaut wird obs passt, wenn ja, wird das nächst längste genommen usw.

Hört sich nach fortschreitender Division an (nennt man doch so, oder?). Du gehst die Liste der Teile also rückwärts durch um möglichst wenig Teile zu nutzen.

Hast Du eine Kombination gefunden, hast Du doch schon mal eine Höchstgrenze der zu verwendenden Teile.

Um die gewünschte Optimierung durchzuführen und möglichst kleine Teile zu verwenden, mußt Du doch nur noch vorwärts durchjackern. Schaust nach der 100, nimmst noch 300 dazu, denn maximal darfst Du ja nur zwei Teile verwenden. Allerdings ist 400 zu kurz, wehalb Du die 100 durch das nächste Teil ersetzt, die 300. Das ergibt auch 600, hat genau 2 Teile und kürzere dazu.

Das wär' mal die "umständliche" Variante. Ich kann mir vorstellen, daß das noch eleganter zu lösen ist. Mir fällt aber nicht ein, wie

[Klotzkopp]

wenn man das dann hat, dann sollten die Stücke möglichst klein sein

Das ist nicht genau genug beschrieben. Was heißt "die Stücke sollen möglichst klein sein"? Soll die durschnittliche Länge der Stücke minimiert werden? Oder die Länge des kürzesten Stücks, oder des längsten? Oder etwas ganz anderes?

Ist 5 - 1 - 1 - 1 "besser" als 2 - 2 - 2 - 2?

[Pointerman]

Moin!

Als ich gelesen habe, daß Du mehrere Bedingungen hast und diese "möglichst gut" erfüllt werden sollen, musste ich spontan an das Simplex-Verfahren denken.

Es dient zur Lösung linearer Optimierungsprobleme.

Vielleicht ist es mit der Kanone auf Spatzen geschossen, aber es kann ja nicht schaden, wenn Du es Dir mal anguckst:

Simplex-Verfahren - Wikipedia

Wir haben das im Studium "zu Fuß" durchgeführt, also mit Stift und Papier, ich kann also nicht mit Code dienen, aber da es sich um ein bekanntes und beliebtes Verfahren handelt müsste sich da schnell was googlen lassen.

Gruß, Maart

[eisdiele]

Das ist nicht genau genug beschrieben. Was heißt "die Stücke sollen möglichst klein sein"? Soll die durschnittliche Länge der Stücke minimiert werden? Oder die Länge des kürzesten Stücks, oder des längsten? Oder etwas ganz anderes?

Ist 5 - 1 - 1 - 1 "besser" als 2 - 2 - 2 - 2?

2 - 2 - 2 - 2 ist besser.

Die großen Teile sollten wenn möglich vermieden werden...

wobei in dem Fall 4 - 4 das optimum wäre.

das simplexverfahren schau ich mir mal an

[eisdiele]

ok, ich hab mir den wikiartikel zum simplexverfahren mal durchgelesen und

versteh nur bahnhof :old

[Pointerman]

Mhh, die Beschreibung vom Simplex ist auch etwas sehr mathematisch...

Ich muss mal zuhause Schauen, ob ich das Skript aus der Vorlesung noch hab, in der wir das behandelt haben, da war es recht anschaulich, mit einfachen Beispielen erklärt.

Hast Du schonmal nach Bibliotheken gesucht, die den Simplex erledigen? Es lohnt sich glaube ich nicht, für Dein Problem dieses Rad neu zu erfinden.

Es müsste ja Funktionen geben, an die Du nur noch die Koeffizienten der Bedingungen übergeben musst. Die müsstest Du dann einmal erstellen, aber das sollte nicht das Problem sein.

Viel Erfolg noch!

P.S.: Fortsdhritte, Erfolge oder andere Lösungswege würden mich interessieren! Man lernt ja immer dazu und nie aus!