Passez à un style qui est ajouté en modifiant pour chaque section.
# -*- coding: utf-8 -*-
n = int(raw_input())
w = map(int,raw_input().split())
v = map(int,raw_input().split())
W = int(raw_input())
################recherche complète naïve########################
def val_tot(i, j):
if i == n:
res = 0
elif j < w[i]:
res = val_tot(i+1,j)
else:
res = max(val_tot(i+1,j), val_tot(i+1, j-w[i]) + v[i])
return res
print val_tot(0, W)
################Note########################
import numpy as np
val_tot_list = -1*np.ones((n+1,W+1))
def val_tot_memo(i, j):
if val_tot_list[i,j] !=-1:
return val_tot_list[i,j]
else:
if i == n:
res = 0
elif j < w[i]:
res = val_tot_memo(i+1,j)
else:
res = max(val_tot_memo(i+1,j), val_tot_memo(i+1, j-w[i]) + v[i])
val_tot_list[i,j] = res
return res
print int(val_tot_memo(0, W))
################Formule graduelle(DP) ########################
## dp[i][j] = dp[i+1][j]( w[i] > j)
## = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i])
## val_tot_list[n,W] = 0
# import numpy as np
val_tot_list = -1*np.ones((n+1,W+1))
val_tot_list[n,:] = 0*val_tot_list[n,:]
for i in range(n-1,-1,-1):
for j in range(W+1):
if i ==n:
val_tot_list[n,j] = 0
else:
if w[i] > j:
val_tot_list[i][j] = val_tot_list[i+1][j]
else:
val_tot_list[i][j] = max(val_tot_list[i+1][j], val_tot_list[i+1][j - w[i]] + v[i])
print int(val_tot_list[0][W])
Le montant du calcul est respectivement O (2 ^ n), O (nW), O (nW). Je n'ai toujours pas l'habitude de formuler soudainement une formule graduelle et de l'amener au code (je vais probablement faire une erreur dans l'indice), alors j'aimerais apprendre à écrire une recherche complète naïve et ensuite faire un mémo.
# -*- coding: utf-8 -*-
s = raw_input()
t = raw_input()
#### dp[i][j]:Longueur maximale de sous-chaîne commune pour les chaînes avant le i-ème de s et avant le j-ème de t
########################## naive #########################
def lcs(i,j):
if i == 0 or j == 0:
return 0
else:
if s[i-1] == t[j-1]:
return lcs(i-1,j-1) + 1
else:
return max(lcs(i-1,j-1+1), lcs(i-1+1,j-1))
print lcs(len(s),len(t))
##########################Note##################################
import numpy as np
lcs_list = -1*np.ones((len(s)+1, len(t)+1),dtype = int)
def lcs_memo(i,j):
if lcs_list[i][j] != -1:
return lcs_list[i][j]
else:
if i == 0 or j == 0:
lcs_list[i][j] = 0
return 0
else:
if s[i-1] == t[j-1]:
lcs_list[i][j] = lcs_memo(i-1,j-1)+1
else:
lcs_list[i][j] = max([lcs_memo(i-1,j-1+1), lcs_memo(i-1+1,j-1)])
return lcs_list[i][j]
print lcs_memo(len(s),len(t))
########################## DP ##################################
import numpy as np
lcs_list = -1*np.ones((len(s)+1, len(t)+1),dtype = int)
lcs_list[0,:] = 0*lcs_list[0,:]
lcs_list[:,0] = 0*lcs_list[:,0] # initialize
for i in range(len(s)):
for j in range(len(t)):
if s[i] == t[j]:
lcs_list[i+1,j+1] = lcs_list[i,j]+1
else:
lcs_list[i+1,j+1] = np.max([lcs_list[i+1,j], lcs_list[i,j+1] ])
print lcs_list[-1,-1]
Il a dit: "Je veux porter une recherche complète naïve et ensuite en prendre note." Cependant, DP a été le plus facile à écrire sur cette question. Contrairement au cas du problème du sac à dos, la boucle de i et j était dans le sens avant, il semble donc que l'initialisation était facile à comprendre.
Les deux autres étaient un peu confus par l'association entre l'argument lcs et l'indexation du tableau.
# -*- coding: utf-8 -*-
n = int(raw_input())
w = map(int,raw_input().split())
v = map(int,raw_input().split())
W = int(raw_input())
#### dp[i][j] :Valeur maximale lorsque le poids est j ou moins dans la combinaison d'articles jusqu'au i-ème,Le résultat final du calcul est d[n][W]
####Valeur initiale d[0][:] = 0, dp[:][0] = 0 (w_i >=Parce que c'est 1)
####La formule graduelle est dp[i+1][j] = max(dp[i][j-k*w[i]] + k*v[i]| k ...avec le nombre d'articles)
##########################Recherche complète############################
def dp(i,j):
if i <= 0 or j <= 0:
return 0
else:
return max([dp(i-1,j-k*w[i-1])+ k*v[i-1] for k in xrange(j//w[i-1] + 1)])
print dp(n, W)
##########################Note############################
import numpy as np
dplist = -1*np.ones((n+1, W+1),dtype=int)
def dp_memo(i,j):
if dplist[i,j] != -1:
return dplist[i,j]
else:
if i <= 0 or j <= 0:
dplist[i,j] = 0
return 0
else:
dplist[i,j] = max([dp_memo(i-1,j-k*w[i-1])+ k*v[i-1] for k in xrange(j//w[i-1] + 1)])
return dplist[i,j]
print dp_memo(n,W)
############################ DP_1 ##########################
import numpy as np
dplist = -1*np.ones((n+1, W+1),dtype=int)
dplist[0,:] = 0
dplist[:,0] = 0
for i in xrange(n):
for j in xrange(W+1):
dplist[i+1,j] = max([dplist[i,j-k*w[i]]+k*v[i] for k in xrange(j//w[i]+1)])
print dplist[n][W]
############################ DP_2 ##########################
# import numpy as np
dplist = -1*np.ones((n+1, W+1),dtype=int)
dplist[0,:] = 0
dplist[:,0] = 0
for i in xrange(n):
for j in xrange(W+1):
if j < w[i]: #### i+Le premier article ne convient plus
dplist[i+1,j] = dplist[i,j]
else:
dplist[i+1,j] = max(dplist[i,j], dplist[i+1,j-w[i]] + v[i]) ####Transformation de l'expression progressive(page 59).Les boucles peuvent être réduites.
print dplist[n][W]
Comme dans le livre des fourmis, si vous écrivez DP tel qu'il est à partir de l'équation graduelle, la boucle sera triplée. Une double boucle peut être créée en évitant les calculs en double en transformant la formule progressive.
Même s'il est transformé en mémo, il est toujours en boucle, il semble donc que le traitement soit de toute façon nécessaire. J'ai utilisé numpy simplement parce qu'il est facile de gérer les tableaux, mais je pense qu'il est préférable de pouvoir écrire uniquement avec les éléments intégrés.
# -*- coding: utf-8 -*-
n = int(raw_input())
w = map(int,raw_input().split())
v = map(int,raw_input().split())
W = int(raw_input())
#########Lorsque l'objectif de DP est changé de valeur en poids en réponse au cas où la contrainte de poids est serrée##########
########## dp[i + 1][j]:Poids minimum lorsque le prix est de j jusqu'au i-ème article
###########La sortie finale est dp[n][j] <=Maximum j qui rencontre W
###########La formule graduelle est dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i])
###########La valeur initiale est dp[0][0] = 0, dp[0][j] = INF =float("INF")
###################Recherche complète################
def dp(i,j):
if i == 0 and j == 0:
return 0
elif j != 0 and i == 0:
return float("INF")
else:
if j < v[i-1]:
return dp(i-1,j)
else:
return min(dp(i-1,j), dp(i-1,j-v[i-1])+w[i-1])
res = 0
for j_val in xrange(sum(v)):
if dp(n,j_val) <= W:
res = j_val
print res
###################Note################
import numpy as np
dplist = np.ones((n+1, sum(v)+1)) * (-1)
def dp_memo(i,j):
if i == 0 and j == 0:
dplist[i,j] = 0
return 0
elif j != 0 and i == 0:
return float("INF")
elif dplist[i,j] != -1:
return dplist[i,j]
else:
if j < v[i-1]:
dplist[i,j] = dp_memo(i-1,j)
return dplist[i,j]
else:
dplist[i,j] = min(dp_memo(i-1,j), dp_memo(i-1,j-v[i-1])+w[i-1])
return dplist[i,j]
res = 0
for j_val in xrange(sum(v)):
if dp_memo(n,j_val) <= W:
res = j_val
print res
################### DP ##################
import numpy as np
dplist = np.ones((n+1, sum(v)+1)) * (-1)
dplist[0,:] = float("INF")
dplist[0,0] = 0
for i in xrange(n):
for j in xrange(sum(v) +1):
if j < v[i]:
dplist[i+1,j] =dplist[i,j]
else:
dplist[i+1,j] = min(dplist[i,j], dplist[i,j-v[i]]+w[i])
res = 0
for j_val in xrange(sum(v)):
if dplist[n,j_val] <= W:
res = j_val
print res
C'est aussi le DP le plus simple à écrire.
Soit l'équation graduelle est dp [i] = hogehoge (dp [i + 1]) ou dp [i + 1] = hogehoge (dp [i]).
Le premier est plus facile lors de l'écriture en utilisant récursif, et le second est plus facile lors de l'écriture avec DP (moins de confusion avec les arguments tableau et fonction). Il semble préférable de changer la formule progressive qui est mise en place en fonction de celle que vous écrivez. Même dans le problème actuel, si dp [i, j] est "le i-ème et les éléments suivants", Puisque l'équation graduelle est dp [i, j] = min (dp [i + 1, j], dp [i + 1, j-v [i]] + w [i]), il est facile d'écrire en récursif.
# -*- coding: utf-8 -*-
n = int(raw_input())
a = map(int,raw_input().split())
m = map(int,raw_input().split())
K = int(raw_input())
import numpy as np
################ dp[i+1][j]:Nombre maximum de i-ths restants lors du passage de j à i-th
################La formule graduelle est dp[i+1][j] = dp[i+1][j-a[i]] -1
################ = -1
################ = m[i] (dp[i][j] >= 0)
################Si tu ne peux pas le faire-Mettre 1
dplist = np.ones((len(a)+1,K+1))*(-1)
dplist[0,0] = 0
for i in range(len(a)):
for j in range(K+1):
if dplist[i,j] >= 0:
dplist[i+1,j] = m[i]
elif dplist[i+1,j-a[i]]<= 0:
dplist[i+1,j] = -1
elif j - a[i] < 0:
dplist[i+1,j] = -1 ####### j - a[i] <Lorsqu'il est à 0, cela ne change pas si j peut être créé même si le i-ème est entré.(i-1)S'il peut être composé à la seconde, il est traité, donc vous n'avez qu'à y penser ici si vous ne pouvez pas le faire.
else:
dplist[i+1][j] = dplist[i+1,j-a[i]] -1
print dplist[n,K] >= 0
DP pour bool semble être un gaspillage.
Dans la valeur booléenne DP à la page 62, il est écrit qu'il s'agit d'une triple boucle car il y a une boucle qui traite combien de a [i] sont insérés (O (K \ sum_i m [i]), mais O (nK). \ sum_i m [i]) semble être correct).
Comme ce fut le cas avec le problème du sac à dos où il n'y a pas de limite sur le nombre de pièces, il semble préférable de penser qu'il y a du gaspillage si une triple boucle apparaît. Pensez à comment éliminer la boucle sur le nombre de a [i].
Dans le DP de booléen, qui est dp [i + 1] [j], si j peut être transformé en i-ème Le processus de "dp [i + 1, j-k * a [i]] == y a-t-il un vrai k?" Est la cause de la triple boucle. Par conséquent, si dp [i + 1] [j] peut être déterminé en utilisant le résultat de dp [i + 1, j-a [i]], la triple boucle devient inutile.
Cependant, si vous n'avez que la valeur booléenne, même si dp [i + 1, ja [i]] = True est donné, vous ne pouvez pas savoir "s'il reste encore un [i]", donc dp [i + 1 , j] ne peut pas être jugé et il devient un écureuil pour tourner la boucle. Ensuite, l'idée semble être d'avoir le nombre de a [i] restants comme tableau.
Il n'y a pas assez de formation pour arriver à ce point à partir de l'énoncé du problème. Est-ce une bonne idée d'écrire (réfléchir) de manière simple (stupide) et de rechercher des améliorations comme ci-dessus (peut-être que ce n'est qu'un problème de base, alors rappelez-vous le modèle).
# -*- coding: utf-8 -*-
import numpy as np
a = map(int,raw_input().split())
#####################page 63#########################
### dp[i]: a[i]La longueur du sous-programme le plus long à la fin
dp = np.ones(len(a),dtype = int) * (-1)
dp[0] = 0
res = 0
for i in range(len(a)):
dp[i] = 1
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i],dp[j] + 1)
res = max(res,dp[i])
print res
#####################page 64: O(n^2)#########################
### dp[i]:La longueur est i+Valeur minimale du dernier élément de la sous-colonne de 1
dp = np.ones(len(a),dtype = int) * float("INF")
n = len(a)
for j in xrange(n):
for i in xrange(n):
if i == 0 or dp[i-1] <a[j]:
dp[i] = min(dp[i],a[j])
print len(dp[dp<float("INF")])
#####################page 65: O(n log n)#########################
import bisect #### C++Plus bas_Pour obtenir le même comportement que lié.
dp = np.ones(len(a),dtype = int) * float("INF")
n = len(a)
for j in xrange(n):
dp[bisect.bisect_left(dp,a[j])] = a[j]
print len(dp[dp<float("INF")])
Les deux derniers sont difficiles.
Pour le moment, dans le cas de la politique de la page 64, si vous tournez la boucle pour j, le tableau se remplira comme suit.
a = {2,1,3,2}
Pensez à la manière dont la table dp doit être mise à jour lorsque vous ajoutez une nouvelle valeur à la fin d'un fichier.
Premièrement, dp [0] est une sous-chaîne croissante de longueur 1, nous devons donc simplement introduire le nouvel élément minimum de a.
dp [1] est le plus petit élément à la fin de la sous-chaîne croissante de longueur 2. La mise à jour ou non de la valeur en ajoutant un nouvel élément peut être décidée par dp [1] dans un avant addition et le plus petit des nouveaux éléments. Cependant, si dp [0] a été mis à jour avec un nouvel élément, le nouvel élément ne peut pas être à la fin de la sous-colonne croissante et est exclu (si i == 0 ou dp [i-1] <a [j]. ] Partie).
Pour dp [2], supposons que dp [1] soit mis à jour avec un nouvel élément. A ce moment, si dp [2] est également mis à jour, il y aura une valeur plus petite à la fin de la sous-chaîne de longueur 2, ce qui est une contradiction. Donc, comparez le nouvel élément avec le dp [1] d'origine uniquement si dp [1] n'a pas été mis à jour.
Donc, en général, si vous ajoutez un nouvel élément à a, dp [i] ne doit être mis à jour avec min (dp [i], a_new) que si dp [i-1] n'a pas été mis à jour avec cette valeur. Bien.
Si la valeur initiale est donnée par INF, il suffit de boucler autour de l'élément de a et de juger depuis le début de dp comme décrit ci-dessus. C'est la réponse en O (n ^ 2).
La méthode utilisant la dichotomie à la page 65 est que la partie à évaluer depuis le début de dp est O (log n). Vous n'avez pas besoin de regarder dp [i] moins de a [j] car la valeur de la séquence finale de dp augmente de façon monotone. Par conséquent, vous pouvez rechercher i tel que dp [i]> = a [j] par bisect.bisect_left (borne inférieure dans STL). À partir de la méthode de recherche, dp [i-1] <a [j], dp [i] = min (dp [i], a [j]) = a [j] est automatiquement satisfaite, donc la condition est jugée. Il peut être mis à jour avec dp [i] = a [j] sans rien faire.
# -*- coding: utf-8 -*-
import numpy as np
n = int(raw_input())
m = int(raw_input())
M = int(raw_input())
####### dp[i][j]Soit le nombre de méthodes en divisant i en j.
#######La formule graduelle est dp[i][j] = dp[i-j][j] + dp[i][j-1]
dp = np.zeros((n+1,m+1),dtype = int)
dp[:,1] = 1
for i in xrange(n+1):
for j in xrange(2,m+1):
if i-j >=0:
dp[i][j] = dp[i][j-1] + dp[i-j][j]
else:
dp[i][j] = dp[i][j-1]
print dp[-1][-1]
Au début, j'ai pensé à la formule progressive, qui était comme penser au reste des boîtes avec le plus grand nombre de boîtes, mais cela n'a pas fonctionné à cause de la duplication. J'aurais peut-être pu éliminer la duplication si je l'avais bien fait, mais ce n'est pas bon car c'était O (mn ^ 2) de toute façon. (Capacité mathématique insuffisante avant la programmation)
J'ai l'habitude de passer des expressions graduelles au code.
# -*- coding: utf-8 -*-
import numpy as np
n = int(raw_input())
m = int(raw_input())
a = map(int,raw_input().split())
M = int(raw_input())
dp = np.zeros((n+1,m+1),dtype = int)
dp[0,:a[0]] = 1
dp[:,0] = 1
for i in xrange(n):
for j in xrange(1,m+1):
if j -1 - a[i] >=0:
dp[i+1][j] = dp[i+1][j-1] + dp[i][j] -dp[i][j-1-a[i]]
else:
dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
print dp[-1][-1]
La formule graduelle est simple, mais comment en réduire la quantité de calcul? Afin d'effacer la triple boucle, il est nécessaire de réécrire la somme avec le montant déjà calculé.
La partie de l'écriture de code dans DP à partir de l'expression graduelle est devenue plus fluide que la puissance d'implémentation. On a l'impression que Kang commence à travailler pour la mauvaise attribution des indices.
Il est encore nécessaire de pratiquer la partie de la formulation d'une formule de calcul appropriée et petite. Quand j'y pense, j'étais un peu faible en théorie des combinaisons depuis le moment où j'ai passé l'examen.
À la fin du chapitre 2, le numéro de la question POJ est répertorié comme un exercice, alors j'aimerais le faire aussi.
Recommended Posts