Anzeige

Optimale Verteilung der Spielkarten auf Druckvorlagen

Allgemeine Spiele-Themen
Benutzeravatar
rubo77
Spielkind
Beiträge: 3

Icon Optimale Verteilung der Spielkarten auf Druckvorlagen

Beitragvon rubo77 » 14. Juli 2021, 18:28

Ich plane ca. 1200 Karten drucken zu lassen für das Open Source Spiel INCANTATA aus dem ZeroNet.

Dabei stoße ich jetzt auf das Problem der Verteilung der Karten auf die unterschiedlichen DIN-A3-Bögen (á 18 Karten). Ich möchte von allen Karten unterschiedliche Mengen drucken und am günstigsten ist es aber, wenn man jeden Bogen z.b. genau 6x drucken lässt. Dabei sind natürlich ein paar Karten, die man nur weniger als 6x drucken will dann zuviel, aber das ist günstiger, als wenn man von einigen Bögen weniger drucken lässt als von den anderen.

Gibt es da einen Algorithmus, in den man seine Karten anzahlen reinschmeißen kann um die optimalen Bögen herauszubekommen?

Dies wäre meine Liste (also z.b 98x die Karte mit der ID 8 drucken):

Code: Alles auswählen

Anzahl  Karten-ID
98   8
42   9
42   7
36   2
34   3
29   12
26   275
24   56
24   51
22   67
22   147
21   24
20   363
20   13
18   1
17   483
17   376
17   364
17   352
17   340
17   298
17   231
17   148
15   76
14   53
14   127
13   97
13   70
13   163
13   143
12   428
11   91
11   6
11   57
11   5
11   466
11   210
11   206
11   111
11   11
10   98
10   85
10   74
10   58
10   44
10   32
10   166
10   162
9   88
9   72
9   4
9   39
9   35
9   195
8   90
8   87
8   64
8   46
8   360
8   233
8   21
8   207
8   18
8   151
7   69
7   54
7   42
7   271
7   177
7   169
7   156
6   814
6   78
6   75
6   48
6   420
6   417
6   41
6   341
6   305
6   278
6   23
6   223
6   209
6   194
6   17
6   167
6   115
6   101
5   99
5   29
5   216
5   190
5   19
5   129
5   124
5   113
4   93
4   89
4   81
4   77
4   63
4   49
4   399
4   37
4   336
4   302
4   251
4   237
4   220
4   20
4   188
4   185
4   158
4   155
4   154
4   15
4   144
4   14
4   136
4   117
4   114
4   100
4   10
3   95
3   83
3   80
3   783
3   779
3   71
3   66
3   505
3   487
3   391
3   36
3   348
3   34
3   332
3   270
3   267
3   244
3   226
3   222
3   213
3   199
3   196
3   191
3   175
3   171
3   165
3   16
3   152
3   141
3   138
3   131
3   120
3   118
3   109
Zuletzt geändert von rubo77 am 16. Juli 2021, 19:10, insgesamt 1-mal geändert.

Benutzeravatar
rajiva
Spielkind
Beiträge: 8

Re: Optimale verteilung der Spielkarten auf Druckvorlagen

Beitragvon rajiva » 16. Juli 2021, 11:32

"Ich plane ca. 1200 Karten drucken zu lassen für das Open Source Spiel INCANTATA aus dem ZeroNet."

Den Link kann ich nicht öffnen aber Du meinst wahrscheinlich diese hier, oder? Willst Du die dann alle selber ausschneiden?
Biber Mania => http://www.biber-mania.eu <= :heart:

Benutzeravatar
rubo77
Spielkind
Beiträge: 3

Re: Optimale verteilung der Spielkarten auf Druckvorlagen

Beitragvon rubo77 » 16. Juli 2021, 19:10

Ja, genau, über diese Plattform wollen wir die Karten verschicken.

Das Spiel INCANTATA ist im ZeroNet entstanden und frei zum Download zur Verfügung. Um die seite im ZeroNet aufzurufen muss man sich den ZeroNet Client herunterladen und starten, dann funktioniert dieser Link: http://127.0.0.1:43110/13VDeMgRgGf73mHs ... fhUKfBvPz/

Der Zeronet.now Mirror ist wohl überlastet.

Die Karten schneiden wir natürlich nicht von Hand. Es gibt Druckereien, die die karten automatisch schneiden und die kanten abrunden. Allerdings ist bei diesen die Preisstaffelung so, dass man es am Günstigsten bekommt, wenn alle Bögen auf din-A3 sind und alle Bögen gleich-oft gedruckt werden sollen, daher meine initiale Frage

Benutzeravatar
rubo77
Spielkind
Beiträge: 3

Re: Optimale Verteilung der Spielkarten auf Druckvorlagen

Beitragvon rubo77 » 17. Juli 2021, 11:59

Ich habe das auch mal hier zur Frage gestellt:
https://math.stackexchange.com/question ... -templates

Die Antwort:

Dies ist eine Variante des [Cutting Stock Problems][1]. Aufgrund der Regel, jedes Blatt genau sechsmal zu drucken, kann man jede Anzahl Karten auf das nächste Vielfache von 6 aufrunden. Ersetze also entsprechend jede Anzahl d durch aufgerundet ⌈d/6⌉ und verwende jede der resultierenden Blätter 6 mal. Nach dieser Transformation beträgt die Gesamtnachfrage in diesem Fall 298, was bedeutet, dass man mindestens 6⌈298/18⌉=6⋅17=102 Blätter benötigt. Eine optimale Lösung besteht darin, die folgenden 17 Blätter jeweils sechsmal zu drucken, wobei die Anzahl der Kopien jeder Karte in Klammern steht, wenn sie 1 überschreitet (z. B. enthält Blatt 3 17 Kopien von Karte 8 und 1 Kopie von Karte 14):

1: 1(3) 2(6) 3(6) 4(2) 10
2: 5(2) 6(2) 7(7) 9(7)
3: 8(17) 14
4: 11(2) 12(5) 13(4) 15 16 17 18(2) 19 20
5: 21(2) 23 24(4) 29 32(2) 34 35(2) 36 37 39(2) 41
6: 42(2) 44(2) 46(2) 48 49 51(4) 53(3) 54(2) 63
7: 56(4) 57(2) 58(2) 64(2) 66 67(4) 69(2) 71
8: 70(3) 72(2) 74(2) 75 76(3) 77 78 80 81 83 85(2)
9: 87(2) 88(2) 89 90(2) 91(2) 93 95 97(3) 98(2) 99 100
10: 101 109 111(2) 113 114 115 117 118 120 124 127(3) 129 131 136 138
11: 141 143(3) 144 147(4) 148(3) 151(2) 152 154 155 158
12: 156(2) 162(2) 163(3) 165 166(2) 167 169(2) 171 175 177(2) 185
13: 188 190 191 194 195(2) 196 199 206(2) 207(2) 209 210(2) 213 216 220
14: 222 223 226 231(3) 233(2) 237 244 251 267 270 271(2) 278 302 305
15: 275(5) 298(3) 332 336 340(3) 341 348 352(3)
16: 360(2) 363(4) 364(3) 376(3) 391 399 417 420 428(2)
17: 466(2) 483(3) 487 505 779 783 814

[1]: https://en.wikipedia.org/wiki/Cutting_stock_problem


Wer ist online?

Mitglieder in diesem Forum: Majestic-12 [Bot] und 32 Gäste