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
|
#!/usr/bin/env python3
Beispiel = []
Beispiel.append("5,23; 4,41; 3,33; 13,13; 9,12; 4,38; 6,34; 5,37; 4,11; 3,74; 10,62")
Beispiel.append("4,14; 3,63; 3,92; 7,95; 5,23; 3,30; 4,86; 15,06")
Beispiel.append("6,96; 5,06; 3,77; 3,95; 3,91; 3,54; 4,26; 4,03; 5,43; 4,04; 4,43; 4,12; 2,78")
# das Beispiel wird geparst
for j in range(len(Beispiel)):
Beispiel[j] = [float(k.replace(",", ".")) for k in Beispiel[j].split("; ")]
# vorgegebene Konstanten in Meter umgerechnet
Faehrenlaenge = 20
Faehrenbreite = 3
Abstand = 0.3
# `abfolge`: Eine Liste mit Längen von Autos
# gibt ein dict zurück, welches "anzahl" und "länge" aller Autos enthält
def strategie_a(Abfolge):
abfolge = Abfolge[:]
# `faehre` hält die Anzahl an Fahrzeugen und deren Gesamtlänge in einem dict
faehre = {"anzahl": [0] * Faehrenbreite, "länge": [0] * Faehrenbreite}
while len(abfolge):
success = False
# Fahrzeuge werden aus der Schlange gepopt
fahrzeug = abfolge.pop()
# jetzt wird das Fahrzeug möglichst weit links eingeordnet
for j in range(Faehrenbreite):
# dazu wird bei allen Parkreihen überprüft, ob das Fahrzeug passt
if fahrzeug + faehre["länge"][j] < Faehrenlaenge - Abstand * (faehre["anzahl"][j] - 1):
faehre["länge"][j] += fahrzeug
faehre["anzahl"][j] += 1
print(str(fahrzeug) + " wurde eingeordnet in die Reihe " + str(j))
success = True
break
if success == False:
print("Das Fahrzeug " + str(fahrzeug) + " hat nicht mehr gepasst")
# ...und abfahren
break
# Wichtig: in `faehre["länge"][x]` ist der Abstand nicht einberechnet
return faehre
# siehe `strategie_a`
def strategie_b(Abfolge):
abfolge = Abfolge[:]
faehre = {"anzahl": [0] * Faehrenbreite, "länge": [0] * Faehrenbreite}
j = 0
while len(abfolge):
success = False
fahrzeug = abfolge.pop()
# Fahrzeuge werden möglichst gleichmäßig von links nach rechts verteilt
for k in range(Faehrenbreite):
l = j + k
if l >= Faehrenbreite:
l -= Faehrenbreite
if fahrzeug + faehre["länge"][l] < Faehrenlaenge - Abstand * (faehre["anzahl"][l] - 1):
faehre["länge"][l] += fahrzeug
faehre["anzahl"][l] += 1
print(str(fahrzeug) + " wurde eingeordnet in Reihe " + str(l))
success = True
break
if success == False:
print("Das Fahrzeug " + str(fahrzeug) + " hat nicht mehr gepasst")
break
j += 1
if j == Faehrenbreite:
j = 0
return faehre
if __name__ == "__main__":
print("\n=== Strategie A ===\n")
print(strategie_a(Beispiel[:]))
print("\n=== Strategie B ===\n")
print(strategie_b(Beispiel[:]))
|
