Lösungsweg Aufgabe 7

[st1974]

Sei

E(n_1,n_2,...,n_k) = \sum_{i=1}^k e(n_i) = \sum_{i=1}^k ( 1+(n_i-3)^2 )

die Gesamtkostenfunktion.

Falls es ein n_i>4 gäbe, dann lohnt sich ein weiterer Schlitten mit drei Geschenken, denn

e(n_i)  =  1+(n_i-3)^2
e(n_i)  =  1+(n_i-6+3)^2
e(n_i)  =  1+(n_i-6)^2 + 6*(n_i-6) + 9
e(n_i)  >=  1+(n_i-6)^2 - 6 + 9
e(n_i)  >  1+(e_n-6)^2 + 1
e(n_i)  >  e(n_i-3) + e(3)

Damit liegt die optimale Lösung (3,3,4) nahe mit E(3,3,4) = 1 + 1 + 2 = 4 .

Bei mehr als 3 Schlitten hätte mindestens ein Schlitten weniger als 3 Geschenke geladen, sonst würde man mindestens 12 Geschenke transportieren. Damit ist für k>3 auf jeden Fall E(n_1,n_2,...,n_k) > 4. Andererseits hätte ein Schlitten bei weniger als 3 Schlitten mindestens 5 Geschenke geladen, so dass die obige Argumentation für n_i>4 gilt.

Also muss die optimale Lösung genau k=3 Schlitten haben. Wenn aber mehr als zwei Schlitten eine von 3 abweichende Anzahl an Geschenken transportieren würden, dann wäre E(n_1,n_2,n_3) wiederum größer als 4. Und die Möglichkeit, dass alle n_i=3 sind, scheidet ebenfalls aus, da dann nur insgesamt 9 Geschenke transportiert werden.

Somit besteht die optimale Beladung aus zwei Schlitten mit je 3 Geschenken -- für den dritten Schlitten bleiben dann genau 4 Geschenke übrig. Das Optimum der Kostenfunktion beträgt 4.

[Raaadi]

Ich habe auf einen Druckfehler getippt, bei Lösungsvorschlag (3) hätte es dann mit (3,4,3) eine optimale Lösung gehabt, insbes. weil ein Lösungsvorschlag, der die 10 Geschenke nicht "respektiert", dann schon von vorneherein "raus" wäre... Aber das wurde dann ausführlichst diskutiert und verworfen. Ohne die konkrete Rechnung überhaupt gemacht zu haben, kommt man schnell darauf, dass jede Abweichung von 3 sehr hart bestraft wird. Die Kosten für die restlichen paar Alternativen kann man bequem im Kopf rechnen, keine kommt an die 4 ran.

[marac]

Wenn man einfach die gegebenen neun Lösungen mal in die Formel einsetzt, stellt man fest, dass dann der niedrigste Wert doppelt vorkommt (bei 4. und bei 7. jeweils 6), schon alleine deshalb konnte nur Antwort 10 richtig sein...

[Fanbusfahrer]

Meine Lösung:

Code:

Die minimalste Lösung findet man z. B. durch Probieren. Kleiner als 3 kann sie nicht sein, weil für zwei Pakete sich 1+2^2=5 ergibt (da dann zwei Schlitten mit je fünf Paketen bepackt werden würden). Damit kann die Anzahl der Pakete 3 betragen. Und tatsächlich mit (3,3,4) findet sich eine Lösung, die mit einem Aufwand von 5 auskommt und damit niedriger als die angegebenen sind.

[DFUx]

Man kann es auf beliebige Geschenkanzahlen N, N > 1 erweitern. 
Wenn N mod 3 = 1 gilt, benötigt man (N-1) / 3 Schlitten, von denen einer mit 4 Geschenken beladen ist und die anderen mit 3.
Wenn N mod 3 = 2 gilt, benötigt man (N+1) / 3 Schlitten, von denen einer mit nur zwei Geschenken beladen ist und die restlichen mit 3 Geschenken.  
Und wenn N mod 3 = 0 benötigt man N/3 Schlitten, die alle mit 3 Geschenken optimal beladen sind.
Der Aufwand beträgt dann (N-1)/3 + 1 bzw. (N+1)/3 + 1 bzw. N/3.

Nur ein Geschenk transportieren zu müssen, erfordert den gleichen Aufwand wie 5 optimal beladene Schlitten und mehr als den doppelten Aufwand vom Transport zweier Geschenke. Im Zweifel werden die Wichtel daher immer überlegen, ob ein weiteres Geschenk für ein Kind nicht günstiger kommt.

[mr.x]

Wenn man einfach die gegebenen neun Lösungen mal in die Formel einsetzt, stellt man fest, dass dann der niedrigste Wert doppelt vorkommt (bei 4. und bei 7. jeweils 6), schon alleine deshalb konnte nur Antwort 10 richtig sein...

So hab ich es auch gemacht

[Feles]

Seien K die Kosten für die Pakete.
So kann man sich schnell überlegen:
2 = K(3,3) < K(a,b) mit a < b, a+b = 6 (sinnvoll nur 2,4 und 1,5)
3 = K(2,3) < K(1,4)
3 = K(3,4) < K(2,5) oder K(1,6)
Abweichungen von 3 werden stärker bestraft.

Außerdem gilt: K(A,B) = K(A) + K(B) mit A, B Mengen von Geschenken und K(0) > 1.

Damit folgt, dass die optimale Lösung so viele Transporte wie Möglich mit 3 Geschenken macht. Entsprechend höchstens ein Transport mit 2 oder 4 Geschenken nötig ist, aber alles andere als Transporte mit diesen Werten ungünstiger ist. Und leere Transporte sind sowieso Geldverschwendung xD

Damit ist 3-3-4 die optimale Lösung.