Algorithmus Längenkombinationen?

[javaCR]

Hallo Java-Community!

Habe folgendes Problem:

Wie ermittle ich alle möglichen Längenkombinationen, wobei eine bestimmte Gesamtlänge nicht überschritten werden darf?

Beispiel:
Kombiniere 3, 4 und 5 Meter lange Stücke miteinander, wobei die Längensumme jeder Kombinationsmöglichkeit 12 Meter nicht überschreiten darf!

Lösung:
A) 55 = 10 m
B) 543 = 12 m
C) 533 = 11 m
D) 444 = 12 m
E) 443 = 11 m
F) 433 = 10 m
G) 3333 = 12 m

Alle möglichen Längenkombinationen hab ich durch "probieren" ermittelt. Schaff es aber nicht, den dieser Lösung zugrunde liegenden Algorithmus zu identifizieren. Kann mir da jemand weiterhelfen?

Danke im Voraus!

 

[SlaterB]

deine Reihenfolge zeigt doch gut den Ablauf,
fange mit 5 an aktueller (erster) Stelle an, gehe zur nächsten,
wenn schon über 12 m dann erstmal Abbruch, sonst genau dasselbe, 5 an die zweite Stelle usw.
bei über 12 m aber nicht wirklich abbrechen, sondern an aktueller Stelle kleinere Werte ausprobieren, 4, 3 usw.

falls es eine Stelle zurückgeht, an dieser ebenfalls auf kleinere Werte wechseln und wieder nur nächsten Wechseln

edit: vor jedem 'Abbruch' das fertige Ergebnis natürlich notieren,
und in Bezug auf untere Antworten: überlegen ob nur kleinergleiche Zahlen als an der vorherigen Stelle erlaubt sind:
54 .. nun an dritter Stelle mit 5 anfangen oder 4

aufwärts 3, 4, 5 geht letztlich genauso wie abwärts 5, 4, 3, ist vielleicht einfacher zu implementieren

 

[Marco13]

Theoretisch und prinzipiell geht das mit dem CombinationIterable von http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html - damit kann man alle Kombinationen durchgehen, und schauen, welche <12m sind, aber gerade durch die Beschränkung auf <12m könnte man das natürlich optimieren...

 

[JohannisderKaeufer]

Die Antwort ist überdies

FRAGWÜRDIG bis FALSCH!

wenn 543 eine Lösung ist, ist dann auch 534 eine Lösung?

ist 53 auch eine Lösung?
53 ist kleiner als 12 und auch eine Kombination.

was ist mit 5?
5<12

543 == 12 & !(543 <12)
will heißen 543 ist 12 lang, aber 12 ist nicht kleiner als 12

ist keine Kombination auch eine Kombination in der Menge der Lösungen

 

[javaCR]

@JohannisderKaeufer

Konkret geht es darum Pakete mit unterschiedlicher Länge in einen Raum mit 12 Metern Gesamtlänge zu packen. Es ist also egal, ob ich zuerst das 5m lange und dann das 4 m lange oder umgekehrt reinpacke! Soll heißen: 543 ist das gleiche wie 534! 53 ist jedoch keine Lösung, da man hier noch ein 3 oder 4m langes Stück reinpacken kann. Das heißt, auch die Anzahl an möglichen Stücken pro Kombinationsmöglichkeit soll maximal sein!

@slaterB
Hab es jetzt nochmal mit 3,4 und 5 und maximaler Gesamtlänge von 16 probiert:

A) 555 = 15
B) 554 = 14
C) 5533 = 16
D) 5443 = 16
E) 5433 = 15
F) 5333 = 14
G) 43333 = 16
H) 33333 = 15

Stimmt das so?
Danke für eure Tipps!

 

[SlaterB]

> Stimmt das so?

inwiefern, das ist ja kein Programm,

dass das alle Möglichkeiten sind, mag ich gern glauben und versichern, wenn auch nicht beschwören,
aber was bringt das?

 

[javaCR]

Ja das weis ich. Wollt nur wissen, ob das alle möglichen Kombinationen sind und ich deinen Ansatz dafür verstanden hab. Werd mich jetzt mal daran machen, das in einem Programm umzusetzen....

Was das bringt?
Naja, ich will die einzelnen zulässigen Längenkombinationen in einer Liste abfragen. Dazu muss ich aber wissen, welche Längenkombinationen überhaupt möglich sind!

 

[Marco13]

Die Antwort ist überdies

FRAGWÜRDIG bis FALSCH!

Falls sich das auf meine Antwort bezog: Im Eröffnungspost war zumindest nicht gesagt, dass die Länge in irgendeiner Hinsicht "maximal" sein sollte. Auch wenn man "null mal 3m" nimmt, sind 12m unterschritten. Aus der "Lösung", die gepostet war, hätte man das zwar theoretisch ablesen können, aber davon auszugehen, dass eine "Lösung", die jemand hier im Forum postet, "richtig" ist, hab' ich mir abgewöhnt

Abgesehen davon ... wenn man 100 Stücke mit Längen >2m hat, und versuchen sollte, die zu einer Länge von 1m zu kombinieren, wäre stures Durchprobieren aller Kombinationen natürlich ... unzweckmäßig. Teheoretisch und prinzipiell war meine Antwort nicht falsch. Aber meinetwegen: Fragwürdig :bahnhof: