Permutation (mögliche Kombinationen)

[BUG]

Zitat von Dejan Vu:

NP-Komplett bleibt NP-Komplett, egal in welcher Sprache. Sofern Du in Prolog keine Optimierungen (pruning) formulierst, wirst Du genauso lange warten.

Stimmt, ich war ein bisschen verwirrt

[Dejan Vu]

Zitat von BUG:

Stimmt, ich war ein bisschen verwirrt

Kein Wunder, bei dem Thread

[juniorA]

Zu Beitrag 17
Nein ganz so einfach ist dieses nicht.
Ich habe maximal 99 Teillängen. Diese will ich auf Paletten legen die eine Länge von 12 Metern haben. Mir geht es jetzt darum, dass ich diese Teile so kombiniere, dass ich möglichst wenige Paletten brauche. Hinzu kommt noch folgende Schwierigkeit dass ich in der Mitte eines Abstellung habe wo das letzte Teil von der 1. Hälfte der Belegung maximal um 40 cm überstehen darf. Teile, deren Länge > 6.4 m sind, fallen von vorne sowieso raus.

[Dejan Vu]

0/1-Knapsack-Problem. NP-Komplett. Kannste nicht durchprobieren. Aber Gott-Sei-Dank kann man das wohl mit linearer Programmierung lösen (wenn die Werte ganzzahlig sind).

[BUG]

Zitat von Dejan Vu:

Aber Gott-Sei-Dank kann man das wohl mit linearer Programmierung lösen (wenn die Werte ganzzahlig sind).

Diesmal bist du verwirrt: Lineare Programmierung mit Ganzzahlen ist im allgemeinen schwer; du meinst vermutlich dynamische Programmierung im Fall vom Rucksack-Problem.
Rucksack-Problem sehe insgesamt auch nicht: Es sollen schließlich keine Teillängen zu hause bleiben und man hat mehrere Paletten.

Mir sieht das eher nach der Optimierungsvariante von Bin-Packing auf: Fülle irgendwas in Behälter, so dass diese nicht überfüllt sind und du möglichst wenig Behälter brauchst. (@juniorA: Passt das auf dein Problem?)
NP-schwer, aber die Approximationsalgorithmen sind nicht so schlecht.

[Dejan Vu]

Zitat von BUG:

Diesmal bist du verwirrt: Lineare Programmierung mit Ganzzahlen ist im allgemeinen schwer; du meinst vermutlich dynamische Programmierung im Fall vom Knapsack-Problem.

Au Backe. Was ich eigentlich sagen wollte: "Also ich wollte sagen, dass etwa zu dieser Zeit die Verwirrung durch die ähm ... und die Verwirrung wird all jene verwirren, die nicht wissen; niemand wird wirklich genau wissen, wo diese kleinen Dinge zu finden sind, die verknüpft sind mit einer Art von Handarbeitszeug, das durch die Verknüpfung verknüpft ist; und zu der Zeit soll ein Freund seines Freundes Hammer verlieren und die Jungen sollen nicht wissen, wo die Dinge die jene Väter erst um 8 Uhr am vorhergehenden Abend dorthin gelegt hatten, kurz vor Glockenschlag."

[Bjoerk]

Zitat von juniorA:

[..]Ich habe maximal 99 Teillängen. Diese will ich auf Paletten legen die eine Länge von 12 Metern haben. Mir geht es jetzt darum, dass ich diese Teile so kombiniere, dass ich möglichst wenige Paletten brauche. Hinzu kommt noch folgende Schwierigkeit dass ich in der Mitte eines Abstellung habe wo das letzte Teil von der 1. Hälfte der Belegung maximal um 40 cm überstehen darf. Teile, deren Länge > 6.4 m sind, fallen von vorne sowieso raus.

Ich gehe bei diesen Problemen meistens so vor, daß ich das Größte auf den Stapel lege. Passt es nicht mehr rein dann in den nächsten Stapel bzw. einen neuen Stapel aufmachen. Das Verlegte aus der Liste rauslöschen. Das ganze solange bis die Liste leer ist. Das mit der Abstellung habe ich nicht verstanden?

[Dejan Vu]

Zitat von Bjoerk:

Das mit der Abstellung habe ich nicht verstanden?

Na. Es sind nicht 12m, sondern 2x6m mit der Einschränkung, das die ersten 6m um maximal 40cm überfüllt sein dürfen. Das schränkt die Möglichkeiten vielleicht ein, aber ich würde das trotzdem analytisch, d.h. mit dynamischer Programmierung machen. Wenn man nicht weiß, wie das geht (ich z.B.) dann schaue ich, ob ich das verstehe und wenn nicht, hol ich mir einen Experten oder einen Studenten von der Uni.