Verschnittproblem

Jetstream · Beiträge: 222

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 !!!

),
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 · Beiträge: 208 Erhaltene Danke: 2

Das ist eine mögliche Lösung (bei allen Schnittstücken sogar mit Rest):

markieren

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 · Beiträge: 222

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:

Sirke · Beiträge: 208 Erhaltene Danke: 2

Okay, hier der Code:

markieren

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 · Beiträge: 2684 Erhaltene Danke: 32

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 · Verfasst: Sa 01.07.06 12:35

Das geht noch optimaler:

markieren

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

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

aim65 · Beiträge: 312 Win 9x, Win XP Delphi 3pro, 7PE

Hach, geht noch besser (barfuß gerechnet):

markieren

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

Der Gesamtverschnitt darf nämlich nur 97cm sein (3120 - 3023cm)

BenBE · Verfasst: Sa 01.07.06 14:40

*g* Jup, sägen wir die 25 nicht an der 11, sondern der 13 ab, haut's hin

^^ Macht dann nebenbei gleich mal 25 cm weniger Verschnit ;-)

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Jetstream · Beiträge: 222

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:

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme