[PYTHON] Étudiez des procédures efficaces pour augmenter la sensibilité des chevalières de 3,5 milliards de fois grâce à une planification dynamique
C'est Noel. Félicitations à Shinobu! Quand j'ai jeté un coup d'œil énergique sur Twitter, j'ai vu les tweets suivants.
D'après la définition de "sensibilité 3000 fois", il semble que la valeur initiale soit 1 au lieu de 0, mais ... eh bien, cela semble pratique pour le calcul. Quoi qu'il en soit, vous pouvez facilement le trouver en faisant un round-robin de 5 $! = 120 $.
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')
Ces quatre moyens sont les réponses. Le calcul est terminé en un instant.
Sensibilité minimale et sensibilité maximale
Trouvons le minimum et le maximum des sensibilités finales, et l'ordre à ce moment.
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("La combinaison la moins sensible:",end="")
print(c)
if kando == max_kando:
print("La combinaison la plus sensible:",end="")
print(c)
min_max()
Output
La combinaison la moins sensible:('A', 'B', 'D', 'C', 'E') -2000.0
La combinaison la moins sensible:('A', 'B', 'D', 'E', 'C') -2000.0
La combinaison la plus sensible:('A', 'C', 'E', 'D', 'B') 11600.0
La combinaison la plus sensible:('A', 'E', 'C', 'D', 'B') 11600.0
Que vous visiez le plus bas ou le plus élevé, la théorie est de gaspiller A (le médicament qui divise par deux), de consacrer toutes les ressources supplémentaires (ou soustraites), puis de le multiplier par cinq. Il semble. Eh bien, en termes de mots, cela ressemble à ça.
3,5 milliards de fois
En passant, il semble y avoir un exemple dans lequel la sensibilité a été multipliée par 3,5 milliards dans le monde. (* Cela semble être un jeu différent d'un certain shinobi anti-démon)
** 3,5 milliards ** ... Je ne peux pas entrer dans un type entier aussi grand.
S'il n'y a pas de limite supérieure aux médicaments orcs, quelle combinaison est efficace pour atteindre une sensibilité de 3,5 milliards? Je sais que si vous continuez à donner le médicament C, il atteindra 3,5 milliards de 3 500 000 000 $ / 2 000 = 1 750 000 $, mais il semble qu'il existe une combinaison plus efficace.
Puisque le médicament de D (5 fois) est trop puissant, il semble préférable d'utiliser le médicament de D autant que possible (un tel algorithme s'appelle la méthode de la cupidité), mais au milieu, divisez 3,5 milliards par l'exposant de 5 Vous devez le mettre sur un «rail» comme celui-ci. Vaut-il mieux utiliser les médicaments A et B en petit nombre et les mettre sur le rail, ou vaut-il mieux les augmenter dans une certaine mesure et les mettre ensuite sur le rail? Il est impossible de vérifier à la main le calcul, et même si vous faites un round robin, la quantité de calcul est trop grande et le soleil se couche.
Méthode de planification dynamique
Dans ce cas, la ** méthode de planification dynamique ** est utilisée. En termes simples, c'est une méthode de calcul qui remplit le tableau tout en laissant des notes des calculs précédents. Si vous accumulez toujours les meilleurs coups, vous pouvez couvrir la table avec les meilleurs coups. Cette fois, la valeur numérique (travail) à comparer peut être unidimensionnelle, mais je souhaite enregistrer l'ordre du médicament sélectionné comme information d'accompagnement, je vais donc préparer un tableau en deux dimensions.
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 est la table qui enregistre les résultats. Enregistrez le nombre d'étapes sur la première ligne et l'ordre sur la deuxième ligne. Nous avons attribué 1 000 000 000 $ comme valeur initiale, ce qui signifie qu'elle est «aveugle». (Le candidat «meilleur coup» dérivé d'une main aveugle est supérieur à 1 000 000 000 $, donc une comparaison minimale ne peut pas en faire le meilleur coup.)
Le reste remplira cela. Si vous n'utilisez que des médicaments C, D et E, vous pouvez remplir le tableau d'une seule manière, mais les médicaments A et B réduisent la sensibilité, le tableau est donc rempli dans la direction opposée. Je ne vois pas beaucoup de ces problèmes, probablement parce que je suis un débutant en compétition, mais y a-t-il quelque chose avec un nom fixe? Pour le moment, nous l'appellerons ici DP bidirectionnel.
Une fonction de DP (sens d'augmentation de la sensibilité) à partir de la gauche.
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
Une fonction de DP (la direction dans laquelle la sensibilité diminue) en partant de la droite.
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
Après cela, répétez simplement ceci de la gauche, de la droite, de la gauche, et ainsi de suite, et le tableau devrait être rempli. Coup d'essai avec une sensibilité jusqu'à 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()
résultat.
[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
se sentir bien. Dans le cas du DP bidirectionnel, vous ne savez pas combien de fois vous devez répéter le zigzag. Pour le moment, l'enquête a été interrompue lorsque les résultats n'ont pas changé même si le nombre était augmenté, donc je ne pense pas qu'il y ait un problème avec les résultats.
Au fait, si vous augmentez max_kando à ** 3,5 milliards ** tel quel, le montant du calcul explosera. Comme mentionné ci-dessus, regardons les nombres qui ont été continuellement divisés par 3,5 milliards à 5. En commençant par le nombre divisé par 5 jusqu'à la 4e puissance, max_kando est un peu plus de 5,6 millions. Il s'agit d'un temps de calcul réaliste.
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
Vous pouvez voir que nous sommes déjà sur les rails à partir de 22 400 $ et ne multiplions que par 5 après cela. Par conséquent, la procédure minimale pour amener une chevalière à la sensibilité ** 3,5 milliards ** avec la médecine de chêne est
CDBDBDEEDDDDDD
Il s'est avéré être. Vous pouvez le faire en seulement 14 étapes!
Ci-dessous, vérifiez.
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