|
Mit diesem kleinen C Programm haben wir die beste Lösung gefunden. Ein paar Annahmen stecken darin: Die linke untere Eintrittskarte schließt bündig mit der Anzeigetafel ab und ragt nicht über sie hinaus. Man bekommt die beste Lösung, wenn man die Anzeigetafel in fünf Teile zerlegt wie auf der Skizze und alle Eintrittskarten in einem Teil gleich orientiert sind (hoch oder quer). Mehr Fälle muss man nicht untersuchen. Ganz genau wissen wir das nicht. Hoffen wir mal, dass es stimmt. Das Programm testet alle Kombinationen durch, wie die Eintrittskarten unter diesen Bedingungen plaziert werden können.
#include <stdio.h>
void schleife(int B,int H,int b[5],int h[5]);
void anzahl(int B,int H,int b[5],int h[5],int m[5],int n[5]);
int min=999999;
int main(int argc, char *argv[]) {
int lage,l;
int i,h[5],b[5];
for (lage=0;lage<32;lage++) {
l = lage;
for (i=0;i<5;i++) {
h[i] = (l%2) ? 105 : 74;
b[i] = (h[i] == 105) ? 74 : 105;
l /= 2;
}
schleife(6420,17740,b,h);
schleife(17740,6420,b,h);
}
}
void schleife(int B,int H,int b[5],int h[5]) {
int n[5],m[5];
for (m[0]=0;m[0]*b[0]<=B+b[0]-1;m[0]++) {
for (m[3]=0;m[3]*b[3]<=B+b[3]-1;m[3]++) {
for (n[0]=0;n[0]*h[0]<=H+h[0]-1;n[0]++) {
for (n[2]=0;n[0]*h[0]+n[2]*h[2]<=H+h[2]-1;n[2]++) {
anzahl(B,H,b,h,m,n);
}
}
}
}
}
void anzahl(int B,int H,int b[5],int h[5],int m[5],int n[5]) {
int i,zahl;
m[1] = (B-(b[0]*m[0]))/b[1];
if (b[0]*m[0]+b[1]*m[1]<B) m[1]++;
if (m[1]<0) m[1]=0;
m[2] = B/b[2];
if (b[2]*m[2]<B) (m[2])++;
m[4] = (B-(b[3]*m[3]))/b[4];
if (b[3]*m[3]+b[4]*m[4]<B) m[4]++;
if (m[4]<0) m[4]=0;
n[1] = (n[0]*h[0])/h[1];
if (n[1]*h[1] < n[0]*h[0]) n[1]++;
n[3] = (H-n[0]*h[0]-n[2]*h[2])/h[3];
if (n[0]*h[0]+n[2]*h[2]+n[3]*h[3]<H) n[3]++;
if (n[3]<0) n[3]=0;
n[4] = (n[3]*h[3])/h[4];
if (n[4]*h[4] < n[3]*h[3]) n[4]++;
zahl = 0;
for (i=0;i<5;i++) zahl += m[i]*n[i];
if(zahl<min) {
min=zahl;
printf("\nH = %d B = %d\n",H,B);
printf("i b h m n\n");
for(i=0;i<5;i++) {
printf("%1d %3d %3d %3d %3d\n",i,b[i],h[i],m[i],n[i]);
}
printf("Bisher beste Loesung: %d\n",min);
}
}
Natürlich hat das Programm nicht diese Skizze gemalt, aber die Ausgabe unten kann man mit der Skizze besser erklären.
Und hier haben wir die Ausgabe des Programms. H und B sind Höhe und Breite der Anzeigetafel (man kann die drei Strefen auch vertikal anordnen), i ist der Index des Feldes in der Anzeigetafel, 0 links oben, 1 rechts oben, 2 mitte, 3 links unten, 4 rechts unten. h und b sind Höhe und Breite der EIntrittskarte (horizontal oder vertikal angeordnet), m ist die Anzahl an Karten in horizontaler Richtung und n in vertikaler Richtung für jeden Teil der Anzeigetafel:
H = 17740 B = 6420
i b h m n
0 105 74 0 0
1 105 74 62 0
2 105 74 62 0
3 105 74 0 240
4 105 74 62 240
Bisher beste Loesung: 14880
H = 6420 B = 17740
i b h m n
0 105 74 0 0
1 105 74 169 0
2 105 74 169 0
3 105 74 0 87
4 105 74 169 87
Bisher beste Loesung: 14703
H = 17740 B = 6420
i b h m n
0 74 105 6 162
1 105 74 57 230
2 105 74 62 0
3 105 74 0 10
4 105 74 62 10
Bisher beste Loesung: 14702
H = 17740 B = 6420
i b h m n
0 74 105 6 167
1 105 74 57 237
2 105 74 62 0
3 105 74 0 3
4 105 74 62 3
Bisher beste Loesung: 14697
H = 17740 B = 6420
i b h m n
0 74 105 6 169
1 105 74 57 240
2 105 74 62 0
3 105 74 0 0
4 105 74 62 0
Bisher beste Loesung: 14694
H = 17740 B = 6420
i b h m n
0 74 105 13 157
1 105 74 52 223
2 105 74 62 0
3 105 74 0 17
4 105 74 62 17
Bisher beste Loesung: 14691
H = 17740 B = 6420
i b h m n
0 74 105 13 162
1 105 74 52 230
2 105 74 62 0
3 105 74 0 10
4 105 74 62 10
Bisher beste Loesung: 14686
H = 17740 B = 6420
i b h m n
0 74 105 13 167
1 105 74 52 237
2 105 74 62 0
3 105 74 0 3
4 105 74 62 3
Bisher beste Loesung: 14681
H = 17740 B = 6420
i b h m n
0 74 105 13 169
1 105 74 52 240
2 105 74 62 0
3 105 74 0 0
4 105 74 62 0
Bisher beste Loesung: 14677
H = 17740 B = 6420
i b h m n
0 74 105 30 167
1 105 74 40 237
2 105 74 62 0
3 105 74 0 3
4 105 74 62 3
Bisher beste Loesung: 14676
H = 17740 B = 6420
i b h m n
0 74 105 30 169
1 105 74 40 240
2 105 74 62 0
3 105 74 0 0
4 105 74 62 0
Bisher beste Loesung: 14670
H = 17740 B = 6420
i b h m n
0 74 105 74 169
1 105 74 9 240
2 105 74 62 0
3 105 74 0 0
4 105 74 62 0
Bisher beste Loesung: 14666
H = 6420 B = 17740
i b h m n
0 74 105 227 40
1 105 74 9 57
2 105 74 169 0
3 105 74 0 30
4 105 74 169 30
Bisher beste Loesung: 14663
H = 6420 B = 17740
i b h m n
0 74 105 200 31
1 105 74 28 44
2 74 105 240 9
3 105 74 0 30
4 105 74 169 30
Bisher beste Loesung: 14662
H = 6420 B = 17740
i b h m n
0 74 105 200 31
1 105 74 28 44
2 105 74 169 30
3 74 105 237 9
4 105 74 2 13
Bisher beste Loesung: 14661
Wer das Programm selbst testen möchte, muss etwas Geduld haben. Auf einem iBook G4 mit 1,2GHz läuft es etwa eine Stunde. |
