Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Verschnittproblem


Jetstream - Do 29.06.06 18:50
Titel: Verschnittproblem
Moin Moin,
ich hab da ein kleines Problem aus der Richtung Operations Research.

In meiner Wohnung liegt inzwischen das Laminat (und es sieht suuuuuper aus !!! :D ),
nur die Scheuerleisten fehlen noch. Die sind inzwischen auch eingekauft, vom Preis
her sind die Teile nicht ohne, 7.19€ pro 2.40 Meter.
Mit den ganzen Befestigungen und Endstücken kommt man auf den gleichen Preis
wie für das gesamte Laminat ... daraus folgt nun mein Problem:

Ich habe sämtliche benötigten Längen ausgemessen, wenn ich jedoch einfach so drauflos
säge, habe ich am Ende extrem viel Verschnitt. Wenn ich jedoch vorher die optimale
Verteilung der Stücke auf die Leisten berechne, muss ich keine Leisten nachkaufen.

Die nach Länge aufsteigend sortierten Stücke sind (in cm):
7 10 25 26 27 28 29 30 42 43 53 63 64 96 117 144 155 162 166 166 176 194 240 240 240 240 240

Summe: 3023 cm
Ich habe 13 Leisten a 240 cm, macht 3120 cm.
Es bleibt also Raum für einen knappen Meter Verschnitt.

Wie gehe ich da ran ?
Gibt es schon einen fertigen Algorithmus in diesem Forum ? Wikipedia ? Google ?
Hab keinen gefunden ...

Oder sieht jemand die Lösung ? solche Leute solls geben :wink:
Alternativ wäre ich sehr glücklich über einen Ansatz für den Algorithmus,
natürlich fällt mir jetzt auch "erstelle alle Kombinationen und nimm die beste" ein,
aber ich hoffe da auf eure Erfahrung im Lösen von Problemen :flehan:

Gruß Jetstream


Sirke - Do 29.06.06 19:52
Das ist eine mögliche Lösung (bei allen Schnittstücken sogar mit Rest):

Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
 
240 = 240
240 = 240
240 = 240
240 = 240
240 = 240
194 + 42 = 236
176 + 53 = 229
166 + 64 = 230
166 + 63 = 229
162 + 43 + 27 = 232
155 + 30 + 29 + 10 = 224
144 + 28 + 26 + 25 = 223
117 + 96 + 7 = 220


Edit: Wird der Code benötigt?


Jetstream - Do 29.06.06 20:11
Danke für die Lösung !

Wäre super, wenn ich mal in deinen Algorithmus schauen könnte :)

// Edit:
Ich kann morgen sägen!! Jippie!!!! :zustimm:

:dance2: :dance: :dance2: :dance: :dance2: :dance: :dance2: :dance: :dance2:


Sirke - Do 29.06.06 20:38
Okay, hier der Code:

Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
 
var i: Integer; // Laufvariable für die 13 Latten
    j: Integer; // Laufvariable für die Stücke
    n: Integer; // Anzahl der Stücke
    sum: Integer; // Summe der Stücke
    a : array[0..26]of Integer; // Array mit den Stücken
    str: String; // Ausgabesting
begin
  a[ 0] := 7;   a[ 1] := 10;
  a[ 2] := 25;  a[ 3] := 26;
  a[ 4] := 27;  a[ 5] := 28;
  a[ 6] := 29;  a[ 7] := 30;
  a[ 8] := 42;  a[ 9] := 43;
  a[10] := 53;  a[11] := 63;
  a[12] := 64;  a[13] := 96;
  a[14] := 117; a[15] := 144;
  a[16] := 155; a[17] := 162;
  a[18] := 166; a[19] := 166;
  a[20] := 176; a[21] := 194;
  a[22] := 240; a[23] := 240;
  a[24] := 240; a[25] := 240;
  a[26] := 240;

  Memo1.Lines.Clear;

  for i := 1 to 13 do // Die 13 Leisten
  begin
    j := 26;
    sum := 0;
    str := '';
    n := 0;
    repeat
      if ((sum + a[j]) <= (240 - 4*n)) and (a[j] > 0) then
      begin
        sum := sum + a[j];
        if n = 0 then str := str + IntToStr(a[j])
                 else str := str + ' + ' + IntToStr(a[j]);
        a[j] := 0;
        n := n + 1;
      end;
      j := j - 1;
    until (j < 0) or (sum = 240);
    Memo1.Lines.Append( IntToStr(i) + '. ' + str + ' = ' + IntToStr(sum) );
  end;

  // Zum Überprüfen, ob noch ein Stück nicht verwendet wurde!
  sum := 0;
  for i := 0 to 26 do
  begin
    sum := sum + a[i];
  end;
  ShowMessage( IntToStr(sum) );


delfiphan - Sa 01.07.06 01:30
Das Problem erinnert stark an das Rucksackproblem und ist höchst wahrscheinlich NP-vollständig. Das heisst: Alle Möglichkeiten durchprobieren (falls du wirklich die optimale Lösung suchst)!


BenBE - Sa 01.07.06 12:35
Das geht noch optimaler:

Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
 
240 = 240
240 = 240
240 = 240
240 = 240
240 = 240
144 + 96 = 240
166 + 64 + 10 = 240
194 + 43 = 237
176 + 53 + 7 = 236
162 + 42 + 27 = 231
117 + 30 + 29 + 28 + 26 + 25 = 230
166 + 63 = 229
155 = 155


122 cm Verschnitt, wobei die ersten 12 Latten insgesamt nur 37cm haben, man also die 85cm der 13. noch wunderbar für andere Dinge nutzen könnte :P


aim65 - Sa 01.07.06 14:26
Hach, geht noch besser (barfuß gerechnet):

Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
 
 1. - 5. = je 240
 6. 194 + 43 = 237
 7. 176 + 64 = 240           *)
 8. 166 + 63 + 10 = 239
 9. 166 + 42 + 30 = 238
10. 162 + 53 + 25 = 240      *)
11. 155 + 27 + 28 + 29 = 239
12. 144 + 96 = 240           *)
13. 117 + 26 + 7 = 150, Reststück 90


Verschnitt 7cm + 90cm an einem Stück
*): Das Sägeblatt sollte verdammt dünn sein :mrgreen:

Edit: @ BenBe: Check mal deine Nr.11 :P
Der Gesamtverschnitt darf nämlich nur 97cm sein (3120 - 3023cm)


BenBE - Sa 01.07.06 14:40
*g* Jup, sägen wir die 25 nicht an der 11, sondern der 13 ab, haut's hin :P^^ Macht dann nebenbei gleich mal 25 cm weniger Verschnit ;-)


Jetstream - Sa 01.07.06 15:24
Der Verschnitt ist und bleibt 97 cm. :wink: Da kann auch keine noch so tolle Schnittmethode etwas ändern.
Am besten hat mir die erste Lösung gefallen, da diese den Verschnitt auf alle Leisten aufteilt.
So kann ich auch mal daneben sägen :nut:


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!