[PHP] Algorithmus zur gleichmäßigen Verteilung

martin

Well-Known Member
Moin

ich bin auf der Suche nach einem Algorithmus welcher mir eine bestimmte (fixe) Menge an unterschiedlich großen Kästchen gleichmäßig auf eine bestimmte (fixe) Menge an Behälter aufteilt.
Z.B.
Anzahl Behälter: 5
Größe Behälter: 8HE
Anzahl Kästchen:
3x4HE 12
1x5HE 5
5x3HE 15
3x1HE 3

Was ich bräuchte wäre jetzt eine Ausgabe der "besten Lösung", also jene wo die Behälter am besten ausgelastet werden, falls das mehrere Kombinationen sind, dann sämtliche Kombinationen immer in der besten Aufteilung. Ich hab's schon mit der Google Suche probiert, aber da sehe ich den Wald vor lauter Bäumen nicht.

Danke für eure Hilfe
 
Danke für deine Antwort ditobbi. Ich habe es jetzt mal mit etwas Code versucht, scheitere aber schon am ersten kleinen Schritt:

Code:
$BEHAELTER = Array(
    1 => Array(),
    2 => Array(),
    3 => Array(),
    4 => Array(),
    5 => Array()
);
const MAX_HE = 75;

const HE_KAESTCHEN = Array(
    21, 21, 21, 21, 21, 21,
    15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
    10, 10, 10,
    6, 6
);

Wenn ich diese Kästchen wie in deinem Link beschrieben einfach der Größe nach in die Behälter verschiebe, dann bekomme ich folgendes:
array (size=5)
1 =>
array (size=4)
0 => int 21
1 => int 21
2 => int 21
3 => int 10
2 =>
array (size=4)
0 => int 21
1 => int 21
2 => int 21
3 => int 10
3 =>
array (size=5)
0 => int 15
1 => int 15
2 => int 15
3 => int 15
4 => int 15
4 =>
array (size=5)
0 => int 15
1 => int 15
2 => int 15
3 => int 15
4 => int 15
5 =>
array (size=6)
0 => int 15
1 => int 15
2 => int 15
3 => int 10
4 => int 6
5 => int 6
Ein Kästchen mit 15 hat nirgends Platz, also ist diese Kombination nicht möglich. Soweit so gut, es muss also die nächste Kombination her. Und genau daran scheitere ich. Wie komme ich an die möglichen Kombinationen?
 
Naiv könnte man alle Teilmengen berechnen, die max 5 Elementa haben und für die die Summe der Elemente max. 75 ist. Also in etwa so etwas (ungetestet)
PHP:
        function all_subsets(array $set, $max_subset_sum, $max_subset_count) {
            if (count($set))
                return array();

            $elem = array_pop($set);
            $prev_subsets = all_subsets($set, $max_subset_sum, $max_subset_count);

            $subsets = $prev_subsets;
            foreach ($prev_subsets as $subset) {
                array_push($subset, $elem);

                if (count($subset) > $max_subset_count)
                    continue;
                if (array_reduce($subset, function($carry, $item) {
                            return $carry + $item;
                        }, 0) > $max_subset_sum)
                    continue;

                array_push($subsets, $subset);
            }

            return $subsets;
        }
 
Zurück
Oben