[PYTHON] Untersuchen Sie effiziente Verfahren, um die Empfindlichkeit weiblicher Ritter mithilfe dynamischer Planung um das 3,5-Milliarden-fache zu erhöhen
Es ist Weihnachten. Glückwunsch an Shinobu! Als ich energisch auf Twitter spähte, sah ich die folgenden Tweets.
Aus der Definition von "Empfindlichkeit 3000-mal" geht hervor, dass der Anfangswert 1 statt 0 ist, aber ... nun, es scheint für die Berechnung zweckmäßig zu sein. Wie auch immer, Sie können es leicht finden, indem Sie ein Round-Robin von $ 5! = 120 $ machen.
import itertools
def kusuri(kando, s):
if s == 'A':
return kando/2
if s == 'B':
return kando - 900
if s == 'C':
return kando + 2000
if s == 'D':
return kando * 5
if s == 'E':
return kando + 500
def main():
chars = "ABCDE"
for c in list(itertools.permutations(chars, 5)):
kando = 0
for cc in c:
kando = kusuri(kando,cc)
if kando == 3000:
print(c)
Output
('B', 'C', 'D', 'E', 'A')
('C', 'A', 'B', 'E', 'D')
('C', 'A', 'E', 'B', 'D')
('C', 'B', 'D', 'E', 'A')
Diese vier Wege sind die Antworten. Die Berechnung ist sofort abgeschlossen.
Minimale Empfindlichkeit und maximale Empfindlichkeit
Lassen Sie uns das Minimum und Maximum der endgültigen Empfindlichkeiten und die Reihenfolge zu diesem Zeitpunkt finden.
def min_max():
chars = "ABCDE"
min_kando = 0
max_kando = 0
for c in list(itertools.permutations(chars, 5)):
kando = 0
for cc in c:
kando = kusuri(kando,cc)
if kando < min_kando:
min_kando = kando
if max_kando < kando:
max_kando = kando
for c in list(itertools.permutations(chars, 5)):
kando = 0
for cc in c:
kando = kusuri(kando,cc)
if kando == min_kando:
print("Die am wenigsten empfindliche Kombination:",end="")
print(c)
if kando == max_kando:
print("Die empfindlichste Kombination:",end="")
print(c)
min_max()
Output
Die am wenigsten empfindliche Kombination:('A', 'B', 'D', 'C', 'E') -2000.0
Die am wenigsten empfindliche Kombination:('A', 'B', 'D', 'E', 'C') -2000.0
Die empfindlichste Kombination:('A', 'C', 'E', 'D', 'B') 11600.0
Die empfindlichste Kombination:('A', 'E', 'C', 'D', 'B') 11600.0
Unabhängig davon, ob Sie das Niedrigere oder das Höhere anstreben, besteht die Theorie darin, A (das Medikament, das sich halbiert) zu verschwenden, alle hinzugefügten Ressourcen (oder subtrahierten Ressourcen) zu verwenden und es dann mit fünf zu multiplizieren. Es scheint, dass. Nun, in Worten, es scheint so.
3,5 Milliarden Mal
Übrigens scheint es ein Beispiel zu geben, bei dem die Empfindlichkeit weltweit um das 3,5-Milliarden-fache erhöht wurde. (* Es scheint ein anderes Spiel zu sein als ein bestimmter Anti-Dämonen-Shinobi)
** 3,5 Milliarden ** ... Ich kann nicht in einen so großen Int-Typ passen.
Wenn es keine Obergrenze für die Medikamente der Orks gibt, welche Kombination ist dann wirksam, um eine Empfindlichkeit von 3,5 Milliarden zu erreichen? Wenn Sie weiterhin C-Medikamente verabreichen, können Sie sehen, dass es 3,5 Milliarden US-Dollar in 3.500.000.000 / 2.000 = 1.750.000 US-Dollar erreichen wird, aber es scheint, dass es eine etwas effizientere Kombination gibt.
Da die Droge von D (5-mal) zu stark ist, scheint es besser, die Droge von D so oft wie möglich zu verwenden (ein solcher Algorithmus wird Giermethode genannt), aber in der Mitte 3,5 Milliarden durch den Exponenten von 5 zu teilen Sie müssen es auf eine "Schiene" wie diese setzen. Ist es besser, die Medikamente A und B in geringer Anzahl zu verwenden und auf die Schiene zu legen, oder ist es besser, sie bis zu einem gewissen Grad zu erhöhen und dann auf die Schiene zu legen? Es ist unmöglich, die Berechnung von Hand zu überprüfen, und selbst wenn Sie ein Round-Robin-Verfahren durchführen, ist der Rechenaufwand zu groß und die Sonne geht unter.
Dynamische Planungsmethode
In diesem Fall wird die ** dynamische Planungsmethode ** verwendet. Einfach ausgedrückt handelt es sich um eine Berechnungsmethode, die die Tabelle ausfüllt und Notizen zu früheren Berechnungen hinterlässt. Wenn Sie immer die besten Züge sammeln, können Sie den Tisch mit den besten Zügen abdecken. Dieses Mal kann der zu vergleichende numerische Wert (Arbeit) eindimensional sein, aber ich möchte die Reihenfolge aufzeichnen, in der das Medikament als Begleitinformation ausgewählt wurde, und werde daher eine zweidimensionale Tabelle erstellen.
def ikisugi():
inf = pow(10,9)
dp = []
max_kando = 3000+10
for i in range(max_kando):
dp.append([])
dp[i].append(inf)
dp[i].append('')
dp[0][0] = 0
dp ist die Tabelle, in der die Ergebnisse aufgezeichnet werden. Notieren Sie die Anzahl der Schritte in der ersten Zeile und die Reihenfolge in der zweiten Zeile. Wir haben $ 1.000.000.000 $ als Anfangswert zugewiesen, was bedeutet, dass es "blind" ist. (Der aus einer blinden Hand abgeleitete Kandidat für den "besten Zug" liegt bei über 1.000.000.000 USD. Ein Mindestvergleich kann ihn also nicht zum besten Zug machen.)
Der Rest wird dies füllen. Wenn Sie nur C-, D- und E-Medikamente verwenden, können Sie die Tabelle auf eine Weise füllen, aber A- und B-Medikamente verringern die Empfindlichkeit, sodass die Tabelle in die entgegengesetzte Richtung gefüllt wird. Ich sehe nicht viele dieser Probleme, wahrscheinlich weil ich ein Anfänger im Wettbewerb bin, aber gibt es etwas mit einem festen Namen? Vorerst nennen wir es hier bidirektionales DP.
Eine Funktion von DP (Richtung zunehmender Empfindlichkeit) beginnend von links.
def left_dp(dp,max_kando):
inf = pow(10,9)
for i in range(500,max_kando):
C = dp[i-2000][0]+1
if i < 2000:
C = inf
D = dp[int(i/5)][0]+1
if i%5 > 0:
D = inf
E = dp[i-500][0]+1
if min(C,D,E) >= dp[i][0]:
continue
if min(C,D,E) == C:
dp[i][0] = C
dp[i][1] = dp[i-2000][1] + 'C'
if min(C,D,E) == D:
dp[i][0] = D
dp[i][1] = dp[int(i/5)][1] + 'D'
if min(C,D,E) == E:
dp[i][0] = E
dp[i][1] = dp[i-500][1] + 'E'
return dp
Eine Funktion von DP (die Richtung, in der die Empfindlichkeit abnimmt) beginnend von rechts.
def right_dp(dp,max_kando):
inf = pow(10,9)
for i in reversed(range(1,int(max_kando/2))):
A = dp[i*2][0]+1
B = dp[i+900][0]+1
if min(A,B) >= dp[i][0]:
continue
if min(A,B) == A:
dp[i][0] = A
dp[i][1] = dp[i*2][1] + 'A'
if min(A,B) == B:
dp[i][0] = B
dp[i][1] = dp[i+900][1] + 'B'
return dp
Danach wiederholen Sie dies einfach von links, von rechts, von links usw., und die Tabelle sollte gefüllt sein. Probetreffer mit einer Empfindlichkeit von bis zu 3000.
def ikisugi():
inf = pow(10,9)
dp = []
max_kando = 3000+10
for i in range(max_kando):
dp.append([])
dp[i].append(inf)
dp[i].append('')
dp[0][0] = 0
for i in range(5):
dp = left_dp(dp,max_kando)
dp = right_dp(dp,max_kando)
for i,dps in enumerate(dp):
if dps[0] < inf:
print(dps,i)
ikisugi()
Ergebnis.
[0, ''] 0
[5, 'EEBAA'] 25
[4, 'EEBA'] 50
[6, 'CBAEBA'] 75
[3, 'EEB'] 100
.
.
.
[7, 'CBEAACE'] 2900
[7, 'EACBEAC'] 2925
[7, 'EACBBCE'] 2950
[7, 'EAEADBC'] 2975
[3, 'CEE'] 3000
wohlfühlen. Bei bidirektionalem DP wissen Sie nicht, wie oft Sie den Zickzack wiederholen sollen. Vorläufig wurde die Untersuchung abgebrochen, als sich die Ergebnisse nicht änderten, auch wenn die Anzahl erhöht wurde. Ich glaube daher nicht, dass es ein Problem mit den Ergebnissen gibt.
Übrigens, wenn Sie "max_kando" auf "3,5 Milliarden" erhöhen, explodiert der Rechenaufwand. Schauen wir uns, wie oben erwähnt, die Zahlen an, die kontinuierlich durch 3,5 Milliarden auf 5 geteilt wurden. Beginnend mit der Zahl geteilt durch 5 bis zur 4. Potenz beträgt max_kando etwas mehr als 5,6 Millionen. Dies ist eine realistische Berechnungszeit.
for i in range(4,10):
j = pow(5,i)
k = int((3500000000/j))
print(dp[k],k)
Output
[10, 'CDBDBDEEDD'] 5600000
[9, 'CDBDBDEED'] 1120000
[8, 'CDBDBDEE'] 224000
[8, 'CDBDCBBB'] 44800
[1000000000, ''] 8960
[1000000000, ''] 1792
Sie können sehen, dass wir bereits ab 22.400 US-Dollar auf den Schienen sind und danach nur noch mit 5 multiplizieren. Daher ist das Mindestverfahren, um eine Ritterin mit Eichenmedizin auf Sensibilität zu bringen ** 3,5 Milliarden **
CDBDBDEEDDDDDD
Es stellte sich heraus. Sie können es in nur 14 Schritten tun!
Überprüfen Sie unten.
C 2000
D 10000
B 9100
D 45500
B 44600
D 223000
E 223500
E 224000
D 1120000
D 5600000
D 28000000
D 140000000
D 700000000
D 3500000000
Recommended Posts