Lösungsweg für Mischkarton´s gesucht !

[Hotti]

Hallo,

Ich arbeite gerade an einem Programm was unter anderem Mischkarton Listen erstellen können soll. Eine Mischkiste kann bis zu 6 Flaschen enthalten, wobei es 1 Ltr und 0,75 Ltr Kartons gibt. Beispiel eine Bestellung besteht aus 11 Flaschen des Artikels 1 und 7 Flaschen des Artikels 2. Ergibt 11-6 =5 (5 in Mischkiste) sowie 7-6=1 (1 in Mischkiste) . In diesem Fall würde die Mischkiste aus 5 Artikel des 1. Artikels sowie 1 des 2. Artikels bestehen.

Hört sich soweit ganz easy an, ab es soll auch mit vielen verschieden Artikel z.B. 20 funktionieren. Und dann gibt es auch noch 1 Ltr Artikel die nicht in die 0,75er Karton passen.

Beispiel: 10 * A, 1*B, 1*C, 9*D, 1*F, 8*G

ergibt
1 Karton Artikel A
1 Karton Artikel D
1 Karton Artikel G

sowie die Mischkarton´s

4x Artikel A 0,75
1x Artikel B 0,75
1x Artikel C 0,75

3x Artikel D 1Ltr
1x Artikel F 1Ltr
2x Artikel G 1Ltr


Weiß jemand ein guten Lösungsweg für die Aufgabe ? Danke.

[Sir Rufo]

Du hast also Artikel mit der Flaschengröße A und der Flaschengröße B und entsprechende Kartons für diese beiden Flaschengrößen. Ja dann verteile diese beiden Größen doch auf die Kartons ;)

[fkerber]

Hi,

darf / kann man denn 0,75 ltr in die 1l-Kartons packen?
Oder wackeln die dann beim Transport zu viel?


Viele Grüße,
Frederic

[Hotti]

Hi Frederic,

danke für deine Frage.
In Ausnahmen / wenn sonst keine andere Lösung möglich wäre ist das durchaus machbar.

z.B (5 * 1 Ltr) und (1 * 0,75) = 1 Mischkarton

aber auch
(3 * 0,75) und (3 * 1 Ltr) wäre möglich
und wenn der letzte Karton nicht voll wird -- macht nix:wink:

Viele Grüße,
Hotti

[p80286]

was ist ein "Mischkarton"?
Enthält er unterschiedliche Flaschengrößen und unterschiedliche Artikel?

Gruß
K-H

Oh, hat sich erledigt, Ja!

[Hotti]

Hi K-H,

ja genau so ist es. Also eine Sache die bei so manchem Logistik Programm vorkommt, wenn es um Verpackungseinheiten geht.

Gruß Hotti

[pelzig]

Rein interessehalber aus #1 zitiert:

"Und dann gibt es auch noch 1 Ltr Artikel die nicht in die 0,75er Karton passen."

Beim "1 Ltr Artikel" scheint noch Luft's in Karton's zu sein :twisted:

Plural und Genetiv sind nicht meine's :twisted:

MfG

[Bjoerk]

Die Aufgabe ist nicht wirklich schwer. (While Flaschen.Count > 0 do ..). Nimm dir eine beliebige Flasche und pack sie in den Kasten, in dem für diese Sorte Flaschen noch der meiste Platz ist. Gibt es keinen Platz mehr dann einen neuen Kasten aufmachen. Die Flasche aus der Liste raus löschen.

[Sir Rufo]

Während der Aufteilung gibt es pro Flaschengröße maximal einen nicht ganz vollen Karton. Wechselt der Artikel, dann werden zuerst ganze Kartons mit dem gleichen Artikel zusammengefasst. Was dann noch übrig bleibt, wird in den Mischkarton gepackt.

[Bjoerk]

Oder die Liste vorher (nach Produkt) sortieren und alles ist gut.

[Sir Rufo]

Zitat:

Zitat von Bjoerk (Beitrag 1284784)

Oder die Liste vorher (nach Produkt) sortieren und alles ist gut.

Und das hilft wobei?

Ich gehe mal davon aus, dass die Informationen in der Art kommen, wie der TE das beschrieben hat:
10xA, 6xB, 2xC

Nach deiner Methode würden wir jetzt 3 Kartons erhalten mit

• 6xA
• 4xA,2xB
• 4xB,2xC

Mit meiner Methode

• 6xA
• 6xB
• 4xA,2xC

Allerdings kann auch mein Ansatz noch weiter verfeinert (verbessert) werden, damit gleiche Artikel möglichst auf nicht zuviele Kartons verteilt werden.

[Bjoerk]

[Saarlännich]Ei, ich hann gemennt, sordiere is immer gudd.[/Saarlännich]. Anyway. Aber hast Recht. Bringt hier nix wenn man zuerst die ganzen Kasten ausm Keller holen will.

[Hotti]

Hi Sir Rufo,

und hast das Prinzip der Sache Perfekt verstanden. Die 6*B aus deinem Beispiel sind ja schon ein komplett gefüllter Karton und sollen nicht auf andere Kartons verteilt werden.

Frage ! Wenn ihr von Listen schreibt, was wäre der beste Datentyp für die Daten Verschieberei !

Hotti

[Bjoerk]

Habs jetzt doch schnell mal gemacht. Ich hab zum Beispiel sowas verwendet. Das muß aber nicht so sein. Das kann man auch mit Arrays machen, falls du dich damit besser auskennst?

Delphi-Quellcode:

type
  TBottleStyle = (bs75, bs100);

const
  cBoxBottlesCount: array[TBottleStyle] of integer = (6, 6); // Wieviel Flaschen passen in den Kasten;

type
  TBottleProduct = (bpA, bpB, bpC, bpD, bpE, bpF, bpG, bpH, bpI, bpJ, bpK);

  TBottle = class // Eine Flasche;
  private
    FProduct: TBottleProduct;
    FStyle: TBottleStyle;
  public
    property Product: TBottleProduct read FProduct write FProduct;
    property Style: TBottleStyle read FStyle write FStyle;
  end;

  TBottles = class // Liste von Flaschen;
  private
    FItems: TObjectList;
    function GetBottle(Index: integer): TBottle;
    function GetCount: integer;
  public
    function Add(Product: TBottleProduct; Style: TBottleStyle): integer;
    procedure Delete(Index: integer);
    procedure Clear;
    procedure AddAsStringsTo(Dest: TStrings);
    function CountAsString: string;
    procedure Assign(Value: TBottles);
    procedure Sort;
    function CanExtractBox(var BottleProduct: TBottleProduct;
      var BottleStyle: TBottleStyle): boolean;
    property Bottle[Index: integer]: TBottle read GetBottle; default;
    property Count: integer read GetCount;
    constructor Create;
    destructor Destroy; override;
  end;

  TBottleBox = class // Ein Kasten bestimmter Flaschengröße;
  private
    FItems: TObjectList;
    FStyle: TBottleStyle;
    function GetBottle(Index: integer): TBottle;
    function GetCount: integer;
  public
    function Add(Product: TBottleProduct): integer;
    procedure Clear;
    function CountAsString: string;
    procedure AddAsStringsTo(Dest: TStrings);
    property Bottle[Index: integer]: TBottle read GetBottle;
    property Style: TBottleStyle read FStyle;
    property Count: integer read GetCount;
    constructor Create(Style: TBottleStyle);
    destructor Destroy; override;
  end;

  TBottleBoxes = class // Kästen;
  private
    FItems: TObjectList;
    function GetBox(Index: integer): TBottleBox;
    function GetCount: integer;
  public
    function Add(Style: TBottleStyle): integer;
    function IndexOfMinCount(Style: TBottleStyle): integer;
    procedure Clear;
    function CountAsString: string;
    procedure AddAsStringsTo(Dest: TStrings);
    procedure Fill(List: TBottles); // Flaschen in Kästen einsortieren;
    property Box[Index: integer]: TBottleBox read GetBox;
    property Count: integer read GetCount;
    constructor Create;
    destructor Destroy; override;
  end;

[sx2008]

mein Vorschlag:
a.) Bestellung nach Produkten sortieren
b.) Phase 1 - alle Produkte durchlaufen und so lange jeweils 6 Flaschen in einen sortenreinen Karton verpacken wie die Reststückzahl größergleich 6 ist.
c.) jetzt gibt es kein Produkt mehr mit einer Stückzahl >= 6; es folgt Phase 2
d.) Produkte sortieren nach absteigendem Volumen (1L zuerst)
e.) jeweils prüfen ob das zu verpackende Produkt (Stückzahl zwischen 1 und 5) einen großen 1L-Karton oder einen kleineren 0,75L-Karton benötigt und alle Flaschen des Produkts in den Karton packen.
f.) weiter mit nächstem Produkt und wie bei e.) verfahren nur dass dabei der letzte halbvolle Karton zuerst vollgemacht werden muss

Schritt e.) und f.) sind programmiertechnisch also das Gleiche. Dieser Schritt wird so lange ausgeführt bis alles verpackt wurde.
Es gibt zwei Phasen:
Phase 1: sortenreine Karton füllen
Phase 2: Mischkartons füllen
optional gibt es noch Phase 3:
prüfen ob 0,75L-Flaschen aus einem Karton für 6*1L in einen noch nicht vollen 6*0,75L-Karton umgepackt werden sollen.
Ggf. sollte man dies schon in Phase 2 berücksichtigen.

[Hotti]

Hi,

vielen Dank für die Antworten und Lösungsvorschläge.

Ich habe diese mal versucht in einem simplen Pascal Programm umzusetzen.
Wie könnte man die Packroutine noch optimieren um logischere Ergebnisse zu erreichen ?

Viele Grüße
Hotti

Code:

program KartonPacker;

uses SysUtils;

type Bestellung = Record
      Menge:Integer;
      Inhalt:Integer;  // 0 für =0,75 und 1 für 1 LTR Flaschen
      Artikel:String;
     end;


TBestellung = Array [0..5] of Bestellung;
Var zahlen: TBestellung  = ((Menge:9;Inhalt:1;Artikel:'A'),   //Beispieldaten
                            (Menge:2;Inhalt:1;Artikel:'B'),
                            (Menge:1;Inhalt:0;Artikel:'C'),
                            (Menge:7;Inhalt:0;Artikel:'D'),
                            (Menge:3;Inhalt:0;Artikel:'F'),
                            (Menge:2;Inhalt:0;Artikel:'G'));

procedure GanzerKarton;
var
  laenge,i,temp: Integer;
  KAnzahl: Integer;
begin
  laenge:=SizeOf(zahlen) div SizeOf(zahlen[0])-1;
  for i:=0 to laenge-1 do
   begin
    KAnzahl:= zahlen[i].Menge div 6;
    if KAnzahl>0 then
      Writeln(KAnzahl,' voller Karton(s) von '+zahlen[i].Artikel);
    zahlen[i].Menge:=zahlen[i].Menge mod 6;
   end;
end;

procedure sortMenge;
var
  laenge,i,j:Integer;
  temp: Bestellung;
begin
  laenge:=SizeOf(zahlen) div SizeOf(zahlen[0])-1;
  for i:=0 to laenge-1 do
    for j:=1 to laenge do
      if zahlen[j-1].Menge > zahlen[j].Menge then
      begin
        temp:=zahlen[j-1];
        zahlen[j-1]:=zahlen[j];
        zahlen[j]:=temp;
      end;
end;

procedure sortInhalt;
var
  laenge,i,j:Integer;
  temp: Bestellung;
begin
  laenge:=SizeOf(zahlen) div SizeOf(zahlen[0])-1;
  for i:=0 to laenge-1 do
    for j:=1 to laenge do
      if zahlen[j-1].Inhalt > zahlen[j].Inhalt then
      begin
        temp:=zahlen[j-1];
        zahlen[j-1]:=zahlen[j];
        zahlen[j]:=temp;
      end;
end;

procedure Packen(z: TBestellung );
var laenge,i,p,k:Integer;
    maxKarton:Integer;
    KartonNr:Integer;
    FlaschenType:Integer;
    Kistevoll:boolean;
 begin
  laenge:=SizeOf(zahlen) div SizeOf(zahlen[0])-1;   // Anzahl der Array Felder
  maxKarton:=0;
  KartonNr:=0;
  Kistevoll:=False;
  for i:=0 to laenge do inc(maxKarton,z[i].Menge);
  maxKarton:=(maxKarton div 6) + 1;
  P:=0;                                             //Aktuelle Position in Array
  while KartonNr<Maxkarton do
   begin
    k:=0; //KartonInhalt
    Kistevoll:=False;
    Inc(KartonNr);
    Writeln('MischKarton ',KartonNr,' beinhaltet: ');
    if z[p].Inhalt=0 then
     begin
     while ((z[p].menge<6) and (p<=laenge)) and (KisteVoll=False) and (z[p].Inhalt=0) do
      begin
       if (K+z[p].Menge<=6) then
        begin
          writeln(z[p].Menge,' ',z[p].Inhalt,' ',z[p].Artikel);
          inc(k,z[p].Menge);
          inc(p);
          if k=6 then
           begin
            KisteVoll:=True;
            k:=0;
           end;
        end else
        begin
         dec(z[p].Menge,6-k);
         writeln(6-k,' ',z[p].Inhalt,' ',z[p].Artikel);
         Kistevoll:=True;
         k:=0;
        end;
      end;
    end;
     if z[p].Inhalt=1 then
     begin
      while ((z[p].menge<6) and (p<=laenge)) and (KisteVoll=False) and (z[p].Inhalt=1) do
      begin
       if K+z[p].Menge<=6 then
        begin
          writeln(z[p].Menge,' ',z[p].Inhalt,' ',z[p].Artikel);
          inc(k,z[p].Menge);
          inc(p);
          if k=6 then
           begin
            KisteVoll:=True;
            k:=0;
           end;
        end else
        begin
         dec(z[p].Menge,6-k);
         writeln(6-k,' ',z[p].Inhalt,' ',z[p].Artikel);
         Kistevoll:=True;
         k:=0;
        end;
      end;
    end;
   end;

end;

procedure ausgabe(z: TBestellung );
var
  i: Integer;
begin
  for i:=0 to (SizeOf(zahlen) div SizeOf(zahlen[0]))-1 do
  begin
    write(z[i].Menge,' ',z[i].Inhalt,' ',z[i].Artikel);
    writeln(',');
  end;
end;

begin
  GanzerKarton;
  sortMenge;
  sortInhalt;
  Writeln('Sortiert:');
  ausgabe(zahlen);
  Packen(zahlen);
  Writeln('Bitte Taste druecken...');Readln;
end.

[Bjoerk]

Habs mal durchlaufen lassen. Schalt mal die Bereichsprüfung an. In der Packen wird p zu groß? Und ist die Sort so richtig (Sollten nicht eher I und J verglichen werden ?

Edit:

Ich meinte eigentlich das:

Delphi-Quellcode:

procedure SortMenge;
var
  I, J: Integer;
  Temp: Bestellung;
begin
  for I := 0 to High(Zahlen) - 1 do
    for J := I + 1 to High(Zahlen) do
      if Zahlen[I].Menge > Zahlen[J].Menge then
      begin
        Temp := Zahlen[I];
        Zahlen[I] := Zahlen[J];
        Zahlen[J] := Temp;
      end;
end;

procedure SortInhalt;
var
  I, J: Integer;
  Temp: Bestellung;
begin
  for I := 0 to High(Zahlen) - 1 do
    for J := I + 1 to High(Zahlen) do
      if Zahlen[I].Inhalt > Zahlen[J].Inhalt then
      begin
        Temp := Zahlen[I];
        Zahlen[I] := Zahlen[J];
        Zahlen[J] := Temp;
      end;
end;

[Hotti]

Hi Bjoerk,

"Sollten nicht eher I und J verglichen werden ?"

Ja da hast du recht.

Danke für deine Optimierungen.

Hotti

[Sir Rufo]

Eigentlich handelt es sich doch um ein einziges Problem:

Flaschen möglichst ohne große Vermischung auf Kästen aufteilen. Dabei spielt die Flaschengröße eigentlich keine Rolle, wenn man den Algorithmus einmal für Flaschen in der Größe A und dann für Flaschen der Größe B durchläuft.

• Zunächst also alle ganzen Kisten pro Artikel rausnehmen
• Pro Flaschengröße eine Liste bilden
• Diese Listen jeweils an den Algorithmus geben
• Die aufgerundete Gesamtanzahl der Flaschen durch Kartonkapazität ergibt die Kartonanzahl
  
  Code:

  2x A, 4x B, 5x C => Ceil( 11 / 6 ) = 2

• Eine Liste mit den Kartons anlegen und nach freier Anzahl absteigend sortieren
  
  Code:

  6x 1
  6x 2

• Die Artikel nach Anzahl absteigend sortieren
  
  Code:

  5x C
  4x B
  2x A

• Durch die Artikel-Liste gehen und immer in den ersten Karton der Karton-Liste füllen
  
  Code:

  5x C in Karton 1 => 6x 2, 1x 1
  4x B in Karton 2 => 2x 2, 1x 1
  2x A in Karton 2 => 1x 1, 0x 2

So müssten sich eigentlich alle Artikel passend einsortieren lassen