Gewichte in Eimer verteilen

23.10.2014, 09:51

Flipdajunk

Gewichte in Eimer verteilen

Hi ich habe eine Aufgabe die ich (für mich) lösen möchte. Nun bin ich schon ein paar Jährchen aus der Uni raus und hab mal wieder alles vergessen.

Man Stelle es sich so vor:
Ich habe 13 Eimer (k) in jeden Eimer (k) Passt ein bestimmtes Gewicht (n), maximal können aber 35kg in alle Eimer zusammen eingefügt warden. Das Gewicht kann portioniert werden:
Eimer 1-2 in 1000g
Eimer 3-5 in 500g
Eimer 6-8 in 100g
Eimer 9-13 in 500g
wieveile verschiedene Zusammensetzungen gibt es?

Eimer 1: 35kg Möglichkeiten 35
Eimer 2: 35kg Möglichkeiten 35
Eimer 3: 7kg Möglichkeiten 14
Eimer 4: 7kg Möglichkeiten 14
Eimer 5: 7kg Möglichkeiten 14
Eimer 6: 2kg Möglichkeiten 20
Eimer 7: 2kg Möglichkeiten 20
Eimer 8: 2kg Möglichkeiten 20
Eimer 9: 3kg Möglichkeiten 6
Eimer 10: 3kg Möglichkeiten 6
Eimer 11: 3kg Möglichkeiten 6
Eimer 12: 3kg Möglichkeiten 6
Eimer 13: 3kg Möglichkeiten 6

Danke für eure Tipps!!!

ach ja, was ich vergas:

Es müssen MINDESTENS 20KG in allen Eimern zusammen sein!

Ehrlichgesagt habe ich KEINE Ahnung wie ich daran gehen soll, ich wollte schonmal versuchen irgendwie Excel zu bemühen, aber jede Möglichkeit aufzuschreiben, da bin ich in 5 Jahren noch damit beschäftigt....

Zwei Beiträge zusammengefasst, damit es nicht so aussieht, als ob schon einer geantwortet hat. Steffen

23.10.2014, 11:22

HAL 9000

Auf diesen Beitrag antworten »

Ich versteh nicht so richtig, was du am Ende willst?

Möchtest du für jedes mögliche Gesamtgewicht von 20 bis 35 kg (in 100g-Schritten) jeweils die Anzahl der Möglichkeiten der (Teilgewichts-)Zuordnung auf alle 13 unterscheidbaren Eimer? Und ich habe das so verstanden, dass die einzelnen Eimer keine Gewichtslimitierung haben, d.h. es könnten auch in jedem der Eimer 35kg passen?

Also wäre bei z.B. bei gewünschten 33.7kg Gesamtgewicht eine mögliche Zuordnung:

Eimer 1: 5kg
Eimer 3: 3.5kg
Eimer 8: 25.2kg

alle anderen Eimer leer.

23.10.2014, 14:39

Flipdajunk

Auf diesen Beitrag antworten »

Unnötiges Vollzitat gelöscht. Steffen

Nein Eimer 8 Hat MAXIMAL 2 kg, in 100g Schritten, also könnte in Eimer 8 Drinne sein:
100g, 200g, 300g, ... 2000g (dies sind die 20 Moglichkeiten)

Ich suche ALLE Möglichkeiten die es gibt bei einer Gesamtmenge von 20-35kg.

23.10.2014, 15:23

HAL 9000

Auf diesen Beitrag antworten »

RE: Gewichte in Eimer verteilen
Aha, dann enthält diese deine Aufstellung NACH der Fragestellung

Zitat:

Original von Flipdajunk
Eimer 1: 35kg Möglichkeiten 35
Eimer 2: 35kg Möglichkeiten 35
Eimer 3: 7kg Möglichkeiten 14
Eimer 4: 7kg Möglichkeiten 14
Eimer 5: 7kg Möglichkeiten 14
Eimer 6: 2kg Möglichkeiten 20
Eimer 7: 2kg Möglichkeiten 20
Eimer 8: 2kg Möglichkeiten 20
Eimer 9: 3kg Möglichkeiten 6
Eimer 10: 3kg Möglichkeiten 6
Eimer 11: 3kg Möglichkeiten 6
Eimer 12: 3kg Möglichkeiten 6
Eimer 13: 3kg Möglichkeiten 6

die Maximalkapazität der Eimer. Schlecht (besser gesagt überhaupt nicht) oben beschrieben, aber jetzt scheint es geklärt.

Übrigens stimmt das mit den Möglichkeiten nicht: Die Eimer dürfen doch auch leer bleiben, oder? Dann ist es nämlich jeweils eine Möglichkeit mehr in jeder Zeile.

------------------------------------------------------------------------------------------

Also gut, mal abstrahiert:

Zitat:

Du suchst die Anzahl der 13-Tupel $\begin{align*} (x_1,\ldots,x_{13}) \end{align*}$ nichtnegativer ganzer Zahlen mit

$\begin{align*} 200 \leq 10\sum_{i\in A} x_i + 5\sum_{i\in B\cup C} x_i + \sum_{i\in D} x_i \leq 350 \end{align*}$

unter den Nebenbedingungen

$\begin{align*} x_i\leq 35 \end{align*}$ für $\begin{align*} i\in A:=\{1,2\} \end{align*}$
$\begin{align*} x_i\leq 14 \end{align*}$ für $\begin{align*} i\in B:=\{3,4,5\} \end{align*}$
$\begin{align*} x_i\leq 6 \end{align*}$ für $\begin{align*} i\in C:=\{9,10,11,12,13\} \end{align*}$ .
$\begin{align*} x_i\leq 20 \end{align*}$ für $\begin{align*} i\in D:=\{6,7,8\} \end{align*}$

Kombinatorisch einigermaßen knifflig, und eine "schöne" Endformel wird man nicht hinkriegen. Allerdings wird man durch geschickte Zerlegung und dann unter Nutzung dieses Teilresultates

Zitat:

Die Anzahl der $\begin{align*} m \end{align*}$ -Tupel $\begin{align*} (y_1,\ldots,y_m) \end{align*}$ nichtnegativer ganzer Zahlen mit Summe $\begin{align*} s \end{align*}$ unter der Nebenbedingung $\begin{align*} y_j\leq r \end{align*}$ für $\begin{align*} j=1,\ldots,m \end{align*}$ lautet

$\begin{align*} u(m,s,r) = \sum_{k=0}^{\left\lfloor \frac{s}{r+1} \right\rfloor} (-1)^k \binom{m}{k} \binom{s-k(r+1)+m-1}{m-1} \end{align*}$ .

Die entsprechende Anzahl Tupel für alle Summen $\begin{align*} \leq s \end{align*}$ mit derselben Nebenbedingung wie eben lautet

$\begin{align*} v(m,s,r) = \sum_{k=0}^{\left\lfloor \frac{s}{r+1} \right\rfloor} (-1)^k \binom{m}{k} \binom{s-k(r+1)+m}{m} \end{align*}$ .

(beides beweisbar mit Siebformel)

diese vermutlich ziemlich gigantische Anzahl zumindest mit dem Computer berechnen können. Stumpfes Brute-Force wird hier wahrscheinlich Jahr(tausend)e dauern.

EDIT: Na so groß ist die Anzahl doch nicht. Ich komme mit der oben angedeuteten Methode letztendlich auf die Tupel-Anzahl $\begin{align*} 62\,157\,644\,684\,275 \end{align*}$ - Denk- und Rechenfehler nicht ausgeschlossen. Besser nicht alle ausdrucken, bereits das Speichern aller Ergebnistupel dürfte gängige Festplatten überfordern. Big Laugh

24.10.2014, 13:18

Flipdajunk

Auf diesen Beitrag antworten »

Ich danke dir vielmals,

ich bin zwar nicht mehr mitgekommen, aber mir reicht die Zahl die am Ende rauskommt um mir Klar darüber zu sein diese Möglichkeiten NICHT in Excel darzustellen!

24.10.2014, 13:43

HAL 9000

Auf diesen Beitrag antworten »

Hier mal noch die Einzelauflistung der Möglichkeiten für genau das Gewicht (linke Spalte):

code:

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:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321:
322:
323:
324:
325:
326:
327:
328:
329:
330:
331:
332:
333:
334:
335:
336:
337:
338:
339:
340:
341:
342:
343:
344:
345:
346:
347:
348:
349:
350:
351:
352:

Gewicht   Möglichkeiten
 0.0               1
 0.1               3
 0.2               6
 0.3              10
 0.4              15
 0.5              29
 0.6              52
 0.7              84
 0.8             125
 0.9             175
 1.0             272
 1.1             416
 1.2             607
 1.3             845
 1.4            1130
 1.5            1598
 1.6            2249
 1.7            3083
 1.8            4100
 1.9            5300
 2.0            7088
 2.1            9461
 2.2           12419
 2.3           15962
 2.4           20090
 2.5           25859
 2.6           33245
 2.7           42248
 2.8           52868
 2.9           65105
 3.0           81447
 3.1          101780
 3.2          126104
 3.3          154419
 3.4          186725
 3.5          228425
 3.6          279111
 3.7          338783
 3.8          407441
 3.9          485085
 4.0          582681
 4.1          699014
 4.2          834087
 4.3          987900
 4.4         1160453
 4.5         1372756
 4.6         1621641
 4.7         1907132
 4.8         2229229
 4.9         2587932
 5.0         3021533
 5.1         3522568
 5.2         4091151
 5.3         4727282
 5.4         5430961
 5.5         6268979
 5.6         7225127
 5.7         8299813
 5.8         9493037
 5.9        10804799
 6.0        12347145
 6.1        14087177
 6.2        16026110
 6.3        18163943
 6.4        20500676
 6.5        23217821
 6.6        26252348
 6.7        29607425
 6.8        33283044
 6.9        37279205
 7.0        41880838
 7.1        46973067
 7.2        52563356
 7.3        58651667
 7.4        65238000
 7.5        72757034
 7.6        81008396
 7.7        90008295
 7.8        99756595
 7.9       110253296
 8.0       122144505
 8.1       135094084
 8.2       149134931
 8.3       164266641
 8.4       180489214
 8.5       198740452
 8.6       218475819
 8.7       239758345
 8.8       262586974
 8.9       286961706
 9.0       314214345
 9.1       343490101
 9.2       374903850
 9.3       408453104
 9.4       444137863
 9.5       483811842
 9.6       526171004
 9.7       571415722
 9.8       619540593
 9.9       670545617
10.0       726963509
10.1       786855948
10.2       850559072
10.3       918061915
10.4       989364477
10.5      1067868188
10.6      1150759642
10.7      1238583375
10.8      1331318377
10.9      1428964648
11.0      1536017863
11.1      1648482610
11.2      1767213679
11.3      1892172778
11.4      2023359907
11.5      2166629081
11.6      2316419155
11.7      2474034166
11.8      2639407323
11.9      2812538626
12.0      3000945265
12.1      3197029095
12.2      3402728437
12.3      3617931245
12.4      3842637519
12.5      4086374611
12.6      4338938231
12.7      4603141785
12.8      4878803761
12.9      5165924159
13.0      5476430170
13.1      5796834769
13.2      6131133368
13.3      6479041037
13.4      6840557776
13.5      7230442496
13.6      7631133152
13.7      8048190889
13.8      8481181028
13.9      8930103569
14.0      9413021689
14.1      9907383818
14.2     10420788101
14.3     10952588431
14.4     11502784808
14.5     12093255222
14.6     12695417617
14.7     13319476283
14.8     13964493418
14.9     14630469022
15.0     15343640736
15.1     16068226987
15.2     16817714800
15.3     17590772371
15.4     18387399700
15.5     19238768470
15.6     20100601948
15.7     20990462179
15.8     21906495448
15.9     22848701755
16.0     23853785188
16.1     24867556216
16.2     25912566409
16.3     26986283052
16.4     28088706145
16.5     29262688184
16.6     30442595199
16.7     31657009246
16.8     32902528895
16.9     34179154146
17.0     35536512724
17.1     36895891706
17.2     38293072665
17.3     39723559926
17.4     41187353489
17.5     42741486756
17.6     44292444678
17.7     45884503988
17.8     47511810671
17.9     49174364727
18.0     50937232057
18.1     52690300397
18.2     54487759278
18.3     56322091510
18.4     58193297093
18.5     60175090428
18.6     62138914027
18.7     64150401860
18.8     66200026575
18.9     68287788172
19.0     70496647918
19.1     72677722638
19.2     74909725255
19.3     77180728578
19.4     79490732607
19.5     81932519862
19.6     84334990137
19.7     86791658481
19.8     89287765983
19.9     91823312643
20.0     94501447077
20.1     97126971582
20.2     99809998422
20.3    102532464420
20.4    105294369576
20.5    108209739143
20.6    111057429918
20.7    113965999389
20.8    116913569566
20.9    119900140449
21.0    123051086481
21.1    126117523861
21.2    129248335764
21.3    132417284549
21.4    135624370216
21.5    139006748271
21.6    142286071154
21.7    145633439071
21.8    149017680339
21.9    152438794958
22.0    156046109183
22.1    159530177166
22.2    163086196610
22.3    166677463427
22.4    170303977617
22.5    174127583161
22.6    177806204300
22.7    181560984237
22.8    185349070476
22.9    189170463017
23.0    193199828413
23.1    197061043335
23.2    201002991584
23.3    204976045435
23.4    208980204888
23.5    213203223151
23.6    217233633706
23.7    221349784113
23.8    225494640970
23.9    229668204277
24.0    234071539440
24.1    238256667694
24.2    242533034887
24.3    246835575118
24.4    251164288387
24.5    255733741999
24.6    260058404011
24.7    264480350182
24.8    268925866111
24.9    273394951798
25.0    278115833551
25.1    282564511711
25.2    287117109607
25.3    291690665972
25.4    296285180806
25.5    301142667313
25.6    305699865869
25.7    310368242992
25.8    315055016162
25.9    319760185379
26.0    324739653067
26.1    329390223008
26.2    334159873967
26.3    338945457328
26.4    343746973091
26.5    348834293149
26.6    353563715587
26.7    358420772348
26.8    363291438179
26.9    368175713080
27.0    373357500111
27.1    378152120348
27.2    383083573450
27.3    388026484974
27.4    392980854920
27.5    398244663826
27.6    403091872080
27.7    408085739306
27.8    413089109998
27.9    418101984156
28.0    423436453769
28.1    428324811565
28.2    433370253762
28.3    438423454105
28.4    443484412594
28.5    448879356858
28.6    453798671218
28.7    458886057589
28.8    463979671990
28.9    469079514421
29.0    474525964930
29.1    479467314337
29.2    484588241566
29.3    489714080064
29.4    494844829831
29.5    500335034527
29.6    505290752538
29.7    510438023476
29.8    515589094133
29.9    520743964509
30.0    526271349139
30.1    531234972056
30.2    536402540532
30.3    541572989161
30.4    546746317943
30.5    552305416743
30.6    557271602674
30.7    562454491415
30.8    567639515661
30.9    572826675412
31.0    578413038538
31.1    583377464895
31.2    588571663663
31.3    593767408534
31.4    598964699508
31.5    604574783915
31.6    609534030775
31.7    614736381702
31.8    619939823492
31.9    625144356145
32.0    630775407261
32.1    635726833235
32.2    640934910034
32.3    646143735234
32.4    651353308835
32.5    657003239059
32.6    661944856311
32.7    667156843478
32.8    672369328667
32.9    677582311878
33.0    683249582157
33.1    688179935894
33.2    693394513233
33.3    698609411114
33.4    703824629537
33.5    709508138408
33.6    714426195737
33.7    719642432504
33.8    724858868171
33.9    730075502738
34.0    735774487027
34.1    740679538238
34.2    745896799976
34.3    751114180252
34.4    756331679066
34.5    762045628128
34.6    766937202772
34.7    772155072593
34.8    777373009962
34.9    782591014879
35.0    788319599978

Neue Frage »

Antworten »

Gewichte in Eimer verteilen

Verwandte Themen