Michael R.: (PHP) Wieviele Artikel passen in ein Paket?

Guten morgen,

Also ich habe folgedes (PHP-)Problem:

Ich muss mittels PHP ausrechnen ob die ausgewählten Artikel in ein paket passen.
Ich habe verschieden Artikel in verschiedenen Größen (verpackt)
Nun muss mir PHP sagen ob die ausgewählten Artikel in das Paket passen (verschieden Paketgrößen verhonden)
Dass ich also eine Schleife von der Größe des kleinsten Paketes bis zu der des Größten laufen lasse und sobald es reinpasst soll er abbrechen und mir sagen welches Paket verwendet werden soll.
Also das mit der Schleife ist ja klar.
Beispiel:

$pakete = array();
$pakete[0] = ["20|20|30"]; //20X20X30cm
$pakete[1] = ["50|60|50"]; //50X60X50cm
$pakete[2] = ["90|120|150"]; //90X120X150cm

foreach ($pakete as $grösse) // Schleife :)

{
  $lbh = explode("|",$grösse); // trennen in länge breite höhe
  $l = $lbh[0]; // Länge
  $b = $lbh[1]; // Breite
  $h = $lbh[2]; // Höhe
  if ($l <= $l_gegeben &&  $h <= $h_gegeben && $b <= $b_gegeben)
  {
   $paketgrösse = $grösse;
   break;
  }
 }

Ich habe jetzt das array $artikel, in denen Höhe Länge und Breite jeweils als einzelnes Element gespeichert ist.
(höhe|länge|breite).
Wie bekomme ich das jetzt hin, dass mir PHP ausrechnet ob das in das kleinste, das nächstgrößte Paket usw reinpast?
Also so dass nachher die Variablen $l_gegeben, $h_gegeben und $b_gegeben dem Umfang des Paketes ergeben, das benötigt werden würde wenn man es am geschicktesten stapelt?

Ich weiss jetzt nicht ob das verständlich war, nochmal kur in einem Satz:
Die Artikel sollen in das kleinste Paket in das Sie reinpassen weil kleineres Paket => Niedrigere Versandkosten.

Ich hab mir schon überlegt, dass ich vielleicht das Volumen ausrechne und das dann am ende wieder zusammenzähl.
Das geht aber auch nicht, weil wenn man die Artikel so Stapelt bleibt ja immer irgendwo ein Leerraum weil die ja nicht alle quaderförmig und gleichgroß sind...

ICh zerbrech mir nun schon seit fast 3 Tagen den Kopf, find aber nichts.
Gibt es nicht zufällig eine Funktion berechnepaketgroesse($array_länge,$array_höhe,$array_breite) *g* ?

Naja wäre nett wenn mir jemand helfen könnte, weiss echt nicht mehr weiter...

Vielen Dank für Tipps, Tricks und Anregungen, Michael.

  1. Hallo!

    Sag mal, wenn Du alle 3 Dimensionen mit http://at2.php.net/manual/de/function.max.php vergleichst, also jene von der Schachtel mit jener des Artikels?

    Oder sollen mehrere Artikel in eine Schachtel?

    Beste Grüße
    Viennamade

    1. Sag mal, wenn Du alle 3 Dimensionen mit http://at2.php.net/manual/de/function.max.php vergleichst, also jene von der Schachtel mit jener des Artikels?

      OK, seit dieser Antwort kann mir hier niemand mehr was übel nehmen. Tut leid .. flüchtiges lesen.

      Beste Grüße
      Viennamade

      1. Wie meinen?
        Ja es sollen mehrere Artikel rein, sonst wärs ja einfach :)
        Und ich weiss natürlich im Vorraus auch nicht wie viele und welche, das muss alles dynamisch sein, sonst könnt ichs ja von hand ausrechnen :)

  2. Hallo Michael,

    Also ich habe folgedes (PHP-)Problem:
    [...]

    Nee, das ist kein PHP-Problem, das ist ein allgemein bekanntes
    Problem fuer das es (noch?) keine optimale Loesung gibt. Was du
    da beschrieben hast nennt sich in der Informatik das
    “Rucksackproblem” und da haben sich schon ganz andere die Koepfe
    dran heiss gedacht ;-) Schau dir das hier doch mal an:

    http://de.wikipedia.org/wiki/Rucksackproblem

    Wenn du bei Google nach “Rucksackproblem” suchst, wirst du sicher
    auch auf einige fertig implementierte “Loesungen” stossen
    (allerdings wohl meist in Java oder C oder C++).

    Grüße,
     CK

    --
    Death is God's way of telling you not to be such a wise guy.
    http://wwwtech.de/
    1. hi!

      Nee, das ist kein PHP-Problem, das ist ein allgemein bekanntes Problem fuer das es
      (noch?) keine optimale Loesung gibt. Was du da beschrieben hast nennt sich in der
      Informatik das “Rucksackproblem” und da haben sich schon ganz andere die Koepfe
      dran heiss gedacht ;-)

      Kaum. Beim Rucksackproblem hat man eine obere Schranke fuer das Volumen, die nicht
      ueberschritten werden darf. Ziel ist es dann, einen Teil der Artikel auszuwaehlen, damit
      das Volumen moeglichst optimal ausgenutzt wird.

      Wenn ich das richtig verstanden habe, geht es Michael aber darum, fuer eine Menge von
      Artikeln das geeignete Paket herauszufinden. Das ist dann allerdings nicht mehr das
      Rucksackproblem.

      bye, Frank!

      --
      Never argue with an idiot. He will lower you to his level and then
      beat you with experience.
      1. Hallo Frank,

        Wenn ich das richtig verstanden habe, geht es Michael aber darum,
        fuer eine Menge von Artikeln das geeignete Paket herauszufinden.
        Das ist dann allerdings nicht mehr das Rucksackproblem.

        Das dargelegte Problem laesst sich problemlos zurueckfuehren auf das
        bereits bekannte Rucksackproblem.

        Grüße,
         CK

        --
        Es gibt keinen Ort, wo der Geist zu finden waere. Er ist wie die Fussspuren der Voegel am Himmel.
        http://wwwtech.de/
        1. hi!

          Wenn ich das richtig verstanden habe, geht es Michael aber darum,
          fuer eine Menge von Artikeln das geeignete Paket herauszufinden.
          Das ist dann allerdings nicht mehr das Rucksackproblem.
          Das dargelegte Problem laesst sich problemlos zurueckfuehren auf das
          bereits bekannte Rucksackproblem.

          Kann sein, ist aber unerheblich. Damit das hier genannte Problem ebenfalls NP-hart ist,
          musst du es auf das Rucksackproblem reduzieren und nicht umgekehrt.

          bye, Frank!

          --
          Never argue with an idiot. He will lower you to his level and then
          beat you with experience.
        2. Hello,

          Das dargelegte Problem laesst sich problemlos zurueckfuehren auf das
          bereits bekannte Rucksackproblem.

          Wird denn beim Rucksackproblem neuerdings Rücksicht auf die Formhaltigkeit genommen? Das wäre mir neu.

          Harzliche Grüße aus http://www.annerschbarrich.de

          Tom

          --
          Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
          Nur selber lernen macht schlau
        3. Ja ich denke auch dass es das Sein wird.
          Weil ich ja eine Schliefe mit allen Paketgrößen laufen lasse und dann da drin schauen will, ob es in das aktuelle Paket (Das das in dem Schleifendurchlauf grad dran ist) passt.
          Das ist dann das Problem.
          Un nu brauch ich ja da ne Ausgabe ob ja oder nein, sodass ich nachher ein Array mit allen hab in dies reinpassen würde und da das kleinste raussuchen kann :)
          Naja, dann lass ichs halt, wird eben das doppelte Porto verlangt wenn das so nicht wirklich lösbar ist...
          Danke euch allen !

          1. Hello,

            Naja, dann lass ichs halt, wird eben das doppelte Porto verlangt wenn das so nicht wirklich lösbar ist...

            Hast Du denn die sechs erforderlichen Abbildungsfunktionen überhaupt schon mal überlegt?

            Da gibts bestimmt auch was, nicht von Bosch, sondern von Google.

            "Orthogonale Abbildungsfunktionen"

            besonders reizvoll finde ich da ja http://elib.tu-darmstadt.de/diss/000213/diss0.pdf
            aber es wird Dir nicht wirklich helfen.

            Harzliche Grüße aus http://www.annerschbarrich.de

            Tom

            --
            Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
            Nur selber lernen macht schlau
          2. Hallo.

            Ja ich denke auch dass es das Sein wird.

            Wenn es später einmal das Sein wird, was ist es denn jetzt?
            MfG, at

            1. Ja ich denke auch dass es das Sein wird.

              Wenn es später einmal das Sein wird, was ist es denn jetzt?

              Das ist umgangssprache hier bei uns, das heisst eben dass ich denke dass es das ist.

              Hm nu wird mir as zu kompliziert :)
              Ich rechne jetzt eben nur nach Gewicht...

              1. Hallo.

                Das ist umgangssprache hier bei uns,

                Ach, ihr Erdlinge ...
                MfG, at

  3. Hello,

    ich kenne da zwei Kapitäe zur See, die sich nach Ihrer DDR-Laufbahn selbstständig gemacht haben und genau diese Probleme mittels C und C++ lösen. Dafür bekommen sie viel Geld. Scheint also ein durchaus ernstzunehmendes Problem zu sein, dass man nicht mal eben im Forum löst.

    Als allererstes würde ich mal einen reinen Volumenvergleich machen. Wenn der schon schief geht, hilft auch kein umgruppieren. Dann muss man das Packet in kleinste Einheiten zerlegen. Wenn es sich um Quaderformen handelt, reichen kleine Würfelstrukturen. Die Dimensionen der Schachteln müssen sich alle in diesem größten gemeinsamen Teiler darstellen lassen. Dabei darf man in der Praxis ruhig ein wenig mogeln. Um eine grobe Annäherung zu bekommen, reichen dafür Würfel mit Kantenlängen von 5% der Paketkantenlängen.

    Dann hat jeder Würfel im Paket einen (byte)-Schalter, ob er benutzt wird oder nicht, denn wo ein Körper ist, kann kein anderer sein. Wenn also eine Zelle, in der #13 (für: wird benutzt durch Schachtel 13) verschoben wird, dann müssen alle anderen mit der #13 mit verschoben werden.

    Bei einem orthogonalen System (und ein Paket ist üblicherweise so eines) benötigst Du nun also Funktionen für die Verschiebung in X,Y,Z-Richtung und Funktionen für die Drehung um die Y,Y,Z-Achse um jeweils 90° .

    Und dann kannst Du Deinen Algorithmus bauen.

    Harzliche Grüße aus http://www.annerschbarrich.de

    Tom

    --
    Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
    Nur selber lernen macht schlau