Hallo,
wir saßen in einer Männerrunde zusammen und habe so über dies und das
geplaudert, und dabei kam das Gespräch auf ein Problem zur
Materialverteilung, für das keiner von uns aus dem Handgelenk eine
Lösung parat hatte.
Ich hätte auch nur gesagt ich schreib ein Skript das alle Möglichkeiten
durchtestet und das beste ausspuckt, aber Brute Force ist ja doof.
Kann mir evtl. jemand von euch sagen wie man das am besten berechnet,
z.B. in Excel oder so?
Das Problem geht so:
- Ich habe eine Kiste, in diese Kiste passen eine bestimmte Anzahl
Behälter.
- Alle Behälter sind gleich groß, unabhängig des Inhalts. Es gibt also
keine Probleme beim Mischen innerhalb der Kiste.
- Jeder Behälter enthält eine Anzahl Teile, die Anzahl hängt vom Teil
ab (z.B. durch Dichte/Größe).
- Jeder Behälter ist Sortenrein, also sind immer 1 bis x des gleichen
Teils enthalten.
- Ein Rezept braucht verschiedene Teile in verschiedenen Anzahlen.
- Es dürfen auch unbesetzte Plätze in der Kiste sein (bzw. leere
Behälter), wenn das Rezept bzw. die Behältergröße ein Teil begrenzt.
Wie finde ich jetzt die optimale Füllung der Kiste heraus, um die
maximale Anzahl an "Kuchen" nach Rezept bauen zu können?
Es geht hier um die beste Möglichkeit die gegebene Kiste auszunutzen,
nicht ein bestimmtes Mengenziel zu schaffen!
Beispiel:
Rezept sagt "1x A, 2x B", in die Kiste passen 30 Behälter, die je 10 A
oder 10 B beinhalten können.
Einfache Lösung: 10 Behälter A und 20 Behälter B ergeben 100 bzw. 200
Teile, ausreichend für 100 "Kuchen".
Jetzt ist aber die Anzahl der Teile pro Behälter variabel, ebenso das
Rezept oder die Größe der Kiste.
Wie geht's z.B. bei:
- Kiste schafft z.B. 27 Behälter
- Ein Behälter schafft 80x A oder 115x B oder 34x C
- Ein Rezept erfordert 3x A, 1x B, 1x C
Wie geht man sowas an? Bei zwei Teilen ist das noch im Kopf machbar,
aber darüber steigts bei mir aus...
Und das ist jetzt bewusst abstrakt, weil es "1 Ei, 100g Zucker und 50g
Mehl" sein könnten, aber auch "1 Stecker und 14 Kontakte" oder "2
Schrauben, 2 Muttern, 4 U-Scheiben, 1 Deckel": es gibt kein konkretes
Problem, nur die allg. Frage nach einem Verfahren zur Bestimmung der
optimalen Aufteilung.
das liest sich für mich wie eine Abänderung des Rucksacksproblems:
https://de.wikipedia.org/wiki/Rucksackproblem
Mit "Mathe" kommt man da nicht weiter. Es braucht einen Algorithmus.
Wenn du die global beste Lösung haben möchtest, bleibt dir nichts
anderes übrig, als alle Lösungen aufzulisten (brute force). Kannst du
diese Liste vielleicht so generieren, dass du frühzeitig aufhören
kannst?
Wenn du nur eine einigermaßen gute Lösung haben möchtest, kannst du mit
einer heuristik rangehen.
Ich würde vermutlich mit Graph-Search rangehen, weil man da Optimalität
und Rechenzeit gut gegeneinander aufwiegen kann. Ein Startpunkt wäre
hier: https://de.wikipedia.org/wiki/Dijkstra-Algorithmus
allerdings musst du dich noch mit den Varianten auseinandersetzen.
A. S. schrieb:> das liest sich für mich wie eine Abänderung des Rucksacksproblems:
LOL es gibt nix was es nicht gibt... Das isses wohl!
A. S. schrieb:> Wenn du die global beste Lösung haben möchtest, bleibt dir nichts> anderes übrig, als alle Lösungen aufzulisten (brute force).
Och.
A. S. schrieb:> Kannst du> diese Liste vielleicht so generieren, dass du frühzeitig aufhören> kannst?
Naja, da es nicht soo viele Kombinationen gibt und viele auch nicht
sinnvoll sind z.B. durch starkes Ungleichgewicht ist das selbst in Basic
unter Dos relativ schnell. (Ja, ich hab da mal was in QBasic
zusammengepfuscht. Aber ob das immer die optimale Lösung liefert, bzw.
ob das die Lösung des Problems wäre ist ja die Frage...)
übrigens: ich bin davon ausgegangen, dass du mehrere Rezepte hast.
Wenn du nur ein Rezept hast, rechnest du, als wäre deine Kiste beliebig
mit Teilen füllbar. Das wäre Schulniveau. Dann rundest du auf "ganze
Behälter" ab.
Für 1 Rezept brauchst Du (mindestens) pro Zutat eine Kiste. du kannst
dann einfach hochzählen.
Du kannst für jede Zutat den fraktionalen Teil einer Kiste bestimmen.
Und damit binär suchen.
Du kannst auch einen term bestimmen, der aber wenig hilfreich ist, da er
mit auf- und abrunden arbeitet.
N=[n*fq] + [n*f2] + ... [n*fx]
Mit N=Anzahl Kisten und f = Anteil der Zutat und []= aufrunden und n =
Anzahl der Kuchen
Bei N=30 und 3 Zutaten ist die Mindestmenge 27/(f1+f2+f3).
Die Maximalmenge entsprechend 30/(f1+f2+f3)
Dazwischen reicht es nummerisch.
A. S. schrieb:> Es braucht einen Algorithmus.
Ist wesentlich einfacher als das Rucksackproblem, da man die optimale
Lösung nach max Anzahl Behälter hat:
Man nimmt einen Behälter von jeder Sorte und berechnet die resultierende
Anzahl Kuchen:
1
A B C
2
Kiste 1 1 1
3
Kuchen 26 115 34
Von der Sorte mit der kleinsten Zahl Kuchen füllt man einen weiteren
Behälter:
Helmut H. schrieb:> Von der Sorte mit der kleinsten Zahl Kuchen füllt man einen weiteren> Behälter:
Die ersten 313 kann man aich mit obiger Formel sparen und ab da
weiterfüllen.
Uups, bei 27 Kisten und 3 Zutaten kann man mit 27-2=25 rechen.
Also mit 25/(1/26+1/115+1/34)=326 starten
Oh, jetzt geht's los!
Danke schonmal für die Ideen!
Also:
Es ging drum, die Kiste (den Rucksack) so zu packen, das die maximale
Anzahl "Kuchen" rauskommt, egal wie viele das sind.
Als Anwendungsfälle sind uns verschiedene Sachen eingefallen,
Backmischungen sind da nur ein naheliegendes Beispiel. ;)
Z.B. Kram für's Zeltlager einpacken, Kindergeburtstagsaustattungen,
Partygetränke, und natürlich auch Bastelzeug, z.B. Bausätze für
Veranstaltungen, wenn man die z.B. in Sortierkästen räumt.
Von daher wird immer nur ein Rezept angewendet, und es wird wohl nur
relativ wenige Zutaten geben, ich würde mal "<10" ansetzen; Anzahl der
Dosen wird auch so 10-50 sein.
Ich muss das mal durchdenken und ausprobieren, aber sieht sehr
interessant aus!
> Wenn du nur ein Rezept hast, rechnest du, als wäre deine Kiste beliebig> mit Teilen füllbar. Das wäre Schulniveau. Dann rundest du auf "ganze> Behälter" ab.
also bei deinem Beispiel
> - Kiste schafft z.B. 27 Behälter> - Ein Behälter schafft 80x A oder 115x B oder 34x C> - Ein Rezept erfordert 3x A, 1x B, 1x C
1
27 = 3/80x + 1/115x + 1/34x
bzw.
1
27 = 0.0756x
damit erhältst du die Anzahl der Kuchen x zu 357,1
Für 357,1 Kuchen brauchst du
* 1071,3 x A (13,4 Behälter)
* 357,1 x B (3,1 Behälter)
* 357,1 x C (10,5 Behälter)
Wenn du also 13 Behälter A, 3xB und 10xC mitnimmst (alle abrunden),
bekommst du dafür:
aus A: 13 * 80 // 3 = 346 Kuchen
aus B: 3 * 115 // 1 = 345 Kuchen
aus C: 10 * 34 // 1 = 340 Kuchen
C ist also limitierend. Dann also den verbleibenden Platz mit einem 11.
Behälter C voll machen und 345 Kuchen backen.
Jens M. schrieb:> z.B. in Excel oder so?
Nur als Ergänzung zu allem richtigen das schon gesagt wurde:
In Excel und LibreOffice Calc gibt es dazu den Solver um solche
Optimierungsfragen zu lösen. Der kann auch Integer Linear Programming
(zu dem dein Problem und der Knapsack gehhört):
https://en.wikipedia.org/wiki/Integer_programming
für mich wäre ganz entscheidend welcher Kuchen wie oft gebacken wird und
wie die Verteilung der Zutaten ist.
z.B:
Kuchen 1: 40% Zutat A; 20% Zutat B; 10% Zutat C; ....
Kuchen 2: 40% Zutat A; 10% Zutat D; 5% Zutat E; ....
Wenn da Kuchen 2 aber 8 von 10 ausmacht, wird man nicht soviel von der
Zutat B sondern eher von D vorhalten müssen.
Zusatzaufgabe:
Jens und Helmut haben ihre leckeren Sahnetorten in ihre jeweiligen
Rucksäcke gepackt. Sagt Jens zu Helmut: 'Gib mir eine deiner
Sahnetorten, dann habe ich genauso viele Sahnetorten wie du.' Helmut
erwidert: 'Ja, aber wenn du mir eine von deinen Sahnetorten gibst, dann
werde ich doppelt so viele Sahnetorten haben wie du.'
Frage: Wer hat anfangs wie viele Sahnetorten dabei? 🍰
Thomas O. schrieb:> Wenn da Kuchen 2 aber 8 von 10 ausmacht, wird man nicht soviel von der> Zutat B sondern eher von D vorhalten müssen.
Nuja, pro Kiste (bzw. deren Belegung) gibt's nur ein Rezept.
Es gibt mehrere Rezepte, aber jedes wird nue gepackt.
Wir wollen die Kirche ja mal im Dorfe lassen...
Yalu X. schrieb:> Ich habe die Vorgehensweise von von A. S. (rava) mal in Python> umgesetzt:
Höhö, das muss ich mal testen! Danke!
Michael M. schrieb:> Wer hat anfangs wie viele Sahnetorten dabei?
5 bzw. 7
Habs im Kopf ausprobiert...
Sainte-Laguë/Schepers und Hare-Niemeyer kommen richtig auf 13 A, 3 B,
11 C.
D'Hondt bevorzugt bekanntlich die größte Partei und bringt eine
suboptimale Lösung.
Joachim L. schrieb:> Warum nicht erst mal gucken, was es da so an Open Source Lösungen gibt?>> https://github.com/search?o=desc&q=Rucksackproblem&s=updated&type=Repositories
Das Problem des TE ist weder das Rucksackproblem noch eine
Spezialisierung oder Verallgemeinerung davon.
Mein oben vorgestelltes Python-Progrämmchen löst das TE-Problem in
O(n·log n). Wenn du einen O(n·log n)-Algorithmus für das Rucksackproblem
findest, bist du der Informatik-King.