当前位置:网站首页>️ 40 000 mots de planification dynamique de la peinture et de l’interprétation, de l’introduction à la maîtrise (Collection recommandée)

️ 40 000 mots de planification dynamique de la peinture et de l’interprétation, de l’introduction à la maîtrise (Collection recommandée)

2021-09-05 11:15:23 Où est le héros?

Articles recommandés qui pourraient vous intéresser
Dessiner un tableau de séquence de résolution
Dessiner une liste de liens
Dessiner la pile de solution
Dessiner la file d'attente
Dessiner une table de hachage
Dessiner un arbre binaire
Dessiner un diagramme
Tri des solutions de dessin

Préface

  「 Planification dynamique 」 En tant que contenu relativement sauvage de l'algorithme , Aucune classification systématique comparée , Ne peut être résumé que par un résumé continu , Catégoriser les différents types .「 Planification dynamique 」(C'est - à - dire: Dynamic programming,Abréviations DP) En mathématiques 、 Sciences de la gestion 、Informatique Et Utilisé en bioinformatique , En décomposant le problème initial en un problème relativement simple 「 Sous - Questions 」 Pour résoudre 「 Questions complexes 」Méthode.
  「 Planification dynamique 」 Est une idée algorithmique : Pour résoudre un problème donné , Nous devons résoudre les différentes parties (C'est - à - dire:「 Sous - Questions 」),Sur la base「 Sous - Questions 」 Pour obtenir la solution du problème initial . Comprendre la planification dynamique , Il faut comprendre. 「 Sous - structure optimale 」 Et 「 Répétez la Sous - Question 」.
   Cet article traite des problèmes de programmation dynamique suivants: , Donner une explication systématique de la base à la profondeur . Commençons par une classification simple , C'est ce que je vais dire aujourd'hui. .


Sautez directement à la fin Participation au vote, Obtenir des avantages exclusifs pour les fans .

Un.、 Problème de récurrence

   Le problème de récurrence comme base de la programmation dynamique , C'est mieux. , C'est un must. , C'est un peu comme une série de nombres en maths du lycée. ,Adoption Valeurs des éléments précédents Exporter Valeur de l'élément courant .

1、 Récursion unidimensionnelle

   Tu grimpes les escaliers. ,Besoin n n n Marchez jusqu'au toit.Chaque fois que tu peux grimper 1 1 1 Ou 2 2 2 Un pas.Combien de façons différentes avez - vous pour monter sur le toit?

   Supposons que nous soyons arrivés à la n n n Escalier de marche , Alors il peut être n − 1 n-1 n1 Par ici. , Ou de n − 2 n-2 n2 Par ici. (Mais, Ça ne peut pas venir de n − 3 n-3 n3 Les marches viennent tout droit. ), Donc si vous atteignez n n n Le nombre de schémas pour l'ordre est f [ n ] f[n] f[n], Alors arrive. n − 1 n-1 n1 L'échelle est f [ n − 1 ] f[n-1] f[n1],Arrivée n − 2 n-2 n2 Étapes C'est f [ n − 2 ] f[n-2] f[n2], On peut donc conclure que : f [ n ] = f [ n − 1 ] + f [ n − 2 ] f[n] = f[n-1] + f[n-2] f[n]=f[n1]+f[n2]  Parmi eux,Quand n = 0 n=0 n=0 Nombre de régimes horaires 1, Représente la situation initiale ; n = 1 n=1 n=1 Nombre de régimes horaires 1, Le représentant a fait un pas , Calcul récursif .
   Ce sont les problèmes de programmation dynamique les plus simples , C'est aussi une série classique. :Série Fibonacci Comment résoudre . Il passe par une formule récursive , Convertit un problème d'ordre exponentiel en un problème linéaire ,La complexité temporelle est O ( n ) O(n) O(n).
  C Le Code de langue est implémenté comme suit: :

int f[1000];
int climbStairs(int n){
    
    f[0] = f[1] = 1;
    for(int i = 2; i <= n; ++i) {
    
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

2、 Récursion bidimensionnelle

  Compte tenu d'un entier non négatif n n n, Avant la formation du triangle Yang hui n n n D'accord. Dans le triangle de Yang hui , Chaque nombre est En haut à gauche Et En haut à droite Somme des nombres .

   Selon la définition du triangle Yang hui , Nous pouvons simplement déformer l'image ci - dessus ,Je l'ai.:

Et donc,, Nous pouvons tirer les conclusions suivantes: :
  1) Tous les nombres du triangle Yang hui peuvent être stockés dans un tableau bidimensionnel , La ligne représente la première dimension , La colonne représente la deuxième dimension ;
  2)No i i i Le nombre d'éléments dans la ligne est i i i - Oui.;
  3)No i i i D'accord No j j j L'élément de colonne satisfait à la formule : c [ i ] [ j ] = { 1 i = 0 c [ i − 1 ] [ j − 1 ] + c [ i − 1 ] [ j ] o t h e r w i s e c[i][j] = \begin{cases} 1 & i=0\\ c[i-1][j-1] + c[i-1][j] & otherwise \end{cases} c[i][j]={ 1c[i1][j1]+c[i1][j]i=0otherwise
   Donc vous pouvez faire une énumération circulaire à deux niveaux .La complexité temporelle est O ( n 2 ) O(n^2) O(n2).
  C Le Code de langue est implémenté comme suit: :

int c[40];
void generate(int n) {
    
    for(int i = 0; i < n; ++i) {
    
        for(int j = 0; j <= i; ++j) {
    
            if(j == 0 || j == i) {
    
                c[i][j] = 1;
            }else {
    
                c[i][j] = c[i-1][j-1] + c[i-1][j];
            }
        }
    }
}

2.、LinéaritéDP

1、 Dépenses minimales

   Chaque indice du tableau sert d'échelle ,No i i i Les marches correspondent à un nombre non négatif de dépenses d'énergie c o s t [ i ] cost[i] cost[i](Indice de 0 C'est parti.). Chaque fois que vous montez une échelle , Dépense la force physique correspondante , Une fois que la valeur physique correspondante a été payée , Vous pouvez choisir Monter une échelle Ou Deux marches. . Trouver le coût minimum pour atteindre le Sommet du plancher .Au début, Vous pouvez sélectionner l'indice comme 0 0 0 Ou 1 1 1 Les éléments de l'échelle initiale.

   Pour passer à la i i i La consommation minimale de la couche est f [ i ] f[i] f[i]. Supposons que la position actuelle soit i i i Escalier d'étage , Alors, c'est seulement possible i − 1 i-1 i1 Couche - toi. ,Ou i − 2 i-2 i2 Couche - toi. ;
    Si i − 1 i-1 i1 Couche - toi. , Il faut consommer de l'énergie. : f [ i − 1 ] + c o s t [ i − 1 ] f[i-1] + cost[i-1] f[i1]+cost[i1];
    Si i − 2 i-2 i2 Couche - toi. , Il faut consommer de l'énergie. : f [ i − 2 ] + c o s t [ i − 2 ] f[i-2] + cost[i-2] f[i2]+cost[i2];
   Le point de départ peut être 0 Ou No 1 Couche, Donc l'équation de transfert d'état : f [ i ] = { 0 i = 0 , 1 min ⁡ ( f [ i − 1 ] + c o s t [ i − 1 ] , f [ i − 2 ] + c o s t [ i − 2 ] ) i > 1 f[i] = \begin{cases} 0 & i=0,1\\ \min ( f[i-1] + cost[i-1], f[i-2] + cost[i-2] ) & i > 1\end{cases} f[i]={ 0min(f[i1]+cost[i1],f[i2]+cost[i2])i=0,1i>1

   La différence entre ce problème et le problème de récurrence initial est que : L'un est la somme des deux premiers termes , L'un est le minimum. . Il s'agit d'un compromis dynamique. , C'est l'idée de la programmation dynamique. .
   Si vous pensiez en arrière, , Il y a deux options à la fois ,La complexité temporelle est O ( 2 n ) O(2^n) O(2n). Après conversion en programmation dynamique , Un seul cycle est nécessaire ,La complexité temporelle est O ( n ) O(n) O(n).
  C Le Code de langue est implémenté comme suit: :

int f[1024];
int min(int a, int b) {
    
    return a < b ? a : b;
}
int minCostClimbingStairs(int* cost, int costSize){
    
    f[0] = 0;
    f[1] = 0;
    for(int i = 2; i <= costSize; ++i) {
    
        f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2]);
    }
    return f[costSize];
}

2、 Sous - segments maximaux et

  Donner un tableau entier n u m s nums nums ,Trouver un sous - Tableau continu avec la somme maximale(Un sous - tableau contient au moins un élément),Renvoie son maximum et.

   Parce qu'un sous - Tableau continu est nécessaire , Donc, pour la i i i Éléments, Le transfert d'état doit être effectué à partir de i − 1 i-1 i1 Éléments transférés .Sur cette base,Oui. f [ i ] f[i] f[i] Exprimé par i i i Valeur maximale à la fin de l'élément No. .
   C'est naturel. , Ce maximum doit contenir n u m s [ i ] nums[i] nums[i] Cet élément, Alors, tu veux l'inclure? n u m s [ i − 1 ] , n u m s [ i − 2 ] , n u m s [ i − 3 ] , . . . , n u m s [ k ] nums[i-1],nums[i-2],nums[i-3],...,nums[k] nums[i1],nums[i2],nums[i3],...,nums[k] Et alors?? En fait, c'est le numéro un. i − 1 i-1 i1 La valeur maximale à la fin de l'élément no est - elle supérieure à zéro? ,C'est - à - dire:Quand f [ i − 1 ] ≤ 0 f[i-1] \le 0 f[i1]0 Heure,Et Avant i − 1 i-1 i1 Il n'est pas nécessaire d'inclure des éléments . Donc il y a une équation de transfert d'état : f [ i ] = { n u m s [ 0 ] i = 0 n u m s [ i ] f [ i − 1 ] ≤ 0 n u m s [ i ] + f [ i − 1 ] f [ i − 1 ] > 0 f[i] = \begin{cases} nums[0] & i = 0 \\ nums[i] & f[i-1] \le 0 \\ nums[i] + f[i-1] & f[i-1] > 0\end{cases} f[i]=nums[0]nums[i]nums[i]+f[i1]i=0f[i1]0f[i1]>0 Après une énumération circulaire de niveau 1 ,Prends - le. m a x ( f [ i ] ) max(f[i]) max(f[i]) C'est la réponse. Un seul cycle est nécessaire ,La complexité temporelle est O ( n ) O(n) O(n).
  C Le Code de langue est implémenté comme suit: :

int dp[30010];
int max(int a, int b) {
    
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize){
    
    int maxValue = nums[0];
    dp[0] = nums[0];
    for(int i = 1; i < numsSize; ++i) {
    
        dp[i] = nums[i];
        if(dp[i-1] > 0) {
    
            dp[i] += dp[i-1];
        }
        maxValue = max(maxValue, dp[i]);
    }
    return maxValue;
}

3、 Séquence monotone la plus longue

  Une longueur donnée est n ( 1 ≤ n ≤ 1000 ) n(1 \le n \le 1000) n(1n1000) Tableau de a i a_i ai, Trouver la longueur de la plus longue séquence progressive .

   Avant d'examiner cette question , Soyons clairs. : Séquence monotone 、 Séquence monotone 、 Séquence monotone maximale .
   Séquence monotone Est une séquence de tableaux qui satisfait à une certaine monotonie ,Par exemple, Séquence d'incrément monotone 、 Séquence monotone décroissante 、 Séquence monotone sans augmentation 、 Séquence monotone non soustractive .Quelques exemples simples:
   Séquence d'incrément monotone :1,2,3,7,9
   Séquence monotone décroissante :9,8,4,2,1
   Séquence monotone sans augmentation :9,8,8,5,2
   Séquence monotone non soustractive :1,2,2,5,5
   Un exemple de séquence d'incréments monotones plus intuitive est le côté d'un escalier .

   Nous pouvons représenter la hauteur de chaque étage de cet escalier par un nombre , Obtenir une séquence d'incréments monotones ,Comme le montre la figure:

   Séquence monotone Se réfère à n'importe quelle séquence de tableau , Sélectionnez les éléments dans l'ordre pour former une nouvelle séquence , Et satisfait à la monotonie . Pour une longueur de n n n Séquence de, Chaque élément peut être sélectionné “Prends - le.” Ou “Non.”, Donc, au mieux, ,Oui. 2 n 2^n 2n Séquence monotone .
  Comme le montre la figure, Représente une séquence :[1,2,4,6,3,5,9]

  Parmi eux [1,2,6] Pour une longueur de 3 Séquence monotone de ,Comme le montre la figure;

  [1,3,6] Pas vraiment. ,Parce que 3 Et 6 N'est pas dans la séquence originale ;[1,4,3] Pas du tout., Parce qu'il ne satisfait pas à la monotonie .
   Séquence monotone la plus longue Se réfère à la séquence originale du tableau , Séquence monotone avec le plus grand nombre d'éléments trouvés .
  Ou [1,2,4,6,3,5,9] Par exemple, Sa séquence monotone la plus longue est :[1,2,4,6,9],La longueur est 5;

  Bien sûr.,C'est possible. [1,2,3,5,9], La longueur est également 5.Insérer la description de l'image ici   Alors,Et puis..., Voyons comment résoudre le problème par programmation dynamique Séquence de progéniteurs la plus longue.
   Pour une séquence de tableau a i ( 1 ≤ i ≤ n ) a_i(1 \le i \le n) ai(1in),Ordre f [ i ] f[i] f[i] Indique par i i i Nombre a i a_i ai Longueur de la plus longue séquence progressive à la fin .Alors, Nous envisageons i i i Nombre a i a_i ai La plus longue séquence progressive à la fin , Le nombre précédent dans cette séquence doit être a j ( 1 ≤ j < i ) a_j(1 \le j < i) aj(1j<i) Un des,Alors..., Si nous savons déjà f [ j ] f[j] f[j],Alors il y a f [ i ] = f [ j ] + 1 f[i] = f[j] + 1 f[i]=f[j]+1.Apparemment., Nous devons encore nous contenter a j < a i a_j < a_i aj<ai Cette restriction progressive .
   Donc nous pouvons obtenir l'équation de transfert d'état : f [ i ] = max ⁡ j = 1 i − 1 ( f [ j ]   ∣   a j < a i ) + 1 f[i] = \max_{j=1}^{i-1} (f[j] \ | \ a_j < a_i) + 1 f[i]=j=1maxi1(f[j]  aj<ai)+1  Ici. f [ j ] f[j] f[j] - Oui. f [ i ] f[i] f[i] Sous - structure de,Et m a x ( f [ j ] ) max(f[j]) max(f[j]) - Oui. f [ i ] f[i] f[i] Sous - structure optimale de , Bien sûr, nous devons penser à une situation , Quand aucune sous - structure optimale n'a été trouvée ,Par exemple: i = 1 i=1 i=1 Ou N'existe pas a j < a i a_j < a_i aj<ai De j j j,En ce moment f [ i ] = 1 f[i] = 1 f[i]=1,Représentation a i a_i ai Est en soi une longueur de 1 1 1 La plus longue séquence progressive de .
   f [ i ] f[i] f[i] Le tableau peut être résolu par une boucle à deux niveaux , Comme le montre le graphique ci - dessous: :

   Nombre de pays f [ . . . ] f[...] f[...] Total O ( n ) O(n) O(n) - Oui., La consommation de transfert d'état est O ( n ) O(n) O(n),Donc la complexité temporelle totale est O ( n 2 ) O(n^2) O(n2), Donc pour ce genre de questions, , Généralement acceptable n n n La gamme est au niveau des milliers ,C'est - à - dire 1000 , 2000 , 3000... 1000, 2000, 3000 ... 1000,2000,3000....Si oui n = 10000 , 100000 n=10000, 100000 n=10000,100000 Situation, Il faut penser à l'optimisation. .
   Problèmes concernant la séquence monotone la plus longue ,Et O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) Algorithme d'optimisation pour , Pour plus de détails, veuillez consulter les articles suivants: :.Algorithme d'écriture silencieuse tard dans la nuit(Vingt.)- Séquence monotone la plus longue .

Trois、2DDP

1、La plus longue sous - séquence commune

   Donner deux séquences de tableaux a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1,a2,...,an Et b 1 , b 2 , . . . , b m b_1, b_2, ..., b_m b1,b2,...,bm,Parmi eux n , m ≤ 1000 n,m \le 1000 n,m1000, Trouver la plus longue sous - séquence commune de deux tableaux .

   Considérez deux séquences de tableaux a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1,a2,...,an Et b 1 , b 2 , . . . , b m b_1, b_2, ..., b_m b1,b2,...,bm,Pour a a a Dans la séquence i i i Éléments a i a_i ai Et b b b Dans la séquence j j j Éléments b j b_j bj,Il y a deux situations:
   ( 1 ) (1) (1) L'égalité, c'est - à - dire a i = = b j a_i == b_j ai==bj Situation, À ce stade, si la séquence préfixe a 1 , a 2 , . . . , a i − 1 a_1, a_2, ..., a_{i-1} a1,a2,...,ai1 Et b 1 , b 2 , . . . , b j − 1 b_1, b_2, ..., b_{j-1} b1,b2,...,bj1 La plus longue sous - séquence commune de ,Notez comme suit: x x x Et si,C'est évident., Ajouter dans les deux séquences a i a_i ai Et b j b_j bj Plus tard, La longueur a encore contribué 1,Alors... a 1 , a 2 , . . . , a i a_1, a_2, ..., a_{i} a1,a2,...,ai Et b 1 , b 2 , . . . , b j b_1, b_2, ..., b_{j} b1,b2,...,bj La plus longue sous - séquence commune de x + 1 x+1 x+1;

   ( 2 ) (2) (2) L'inégalité est a i ≠ b j a_i \neq b_j ai=bj Situation, À ce stade, nous pouvons diviser le problème en deux sous - problèmes plus petits ,C'est - à - dire: Retirer séparément a i a_i ai Et b j b_j bj Situation,Comme le montre la figure:

  Enlevez a i a_i ai Plus tard, Le problème se transforme en recherche : a 1 , a 2 , . . . , a i − 1 a_1, a_2, ..., a_{i-1} a1,a2,...,ai1 Et b 1 , b 2 , . . . , b j b_1, b_2, ..., b_{j} b1,b2,...,bj La plus longue sous - séquence commune de ;
  Enlevez b j b_j bj Plus tard, Le problème se transforme en recherche : a 1 , a 2 , . . . , a i a_1, a_2, ..., a_{i} a1,a2,...,ai Et b 1 , b 2 , . . . , b j − 1 b_1, b_2, ..., b_{j-1} b1,b2,...,bj1 La plus longue sous - séquence commune de ;
   Sur la base de la discussion des deux cas ci - dessus ,Nous avons découvert,À tout moment, Nous supplions tous a a a Préfixe Et b b b La plus longue séquence publique de préfixes pour , Donc vous pouvez définir l'état :Avec f [ i ] [ j ] f[i][j] f[i][j] Représentation a 1 , a 2 , . . . , a i a_1, a_2, ..., a_{i} a1,a2,...,ai Et b 1 , b 2 , . . . , b j b_1, b_2, ..., b_{j} b1,b2,...,bj La plus longue sous - séquence commune de .
   Dans l'état de la conception , Nous avons conçu des transitions d'état invisibles ,L'équation de transfert d'état est la suivante: f [ i ] [ j ] = { 0 i = 0   o r   j = 0 f [ i − 1 ] [ j − 1 ] + 1 i , j > 0 , a i = b j max ⁡ ( f [ i ] [ j − 1 ] , f [ i − 1 ] [ j ] ) i , j > 0 , a i ≠ b j f[i][j] = \begin{cases}0 & i=0\ or\ j=0 \\ f[i-1][j-1] + 1 & i,j>0,a_i=b_j \\ \max(f[i][j-1], f[i-1][j]) & i,j>0,a_i \neq b_j\end{cases} f[i][j]=0f[i1][j1]+1max(f[i][j1],f[i1][j])i=0 or j=0i,j>0,ai=bji,j>0,ai=bj  Pour i = 0 i=0 i=0 Ou j = 0 j=0 j=0 Représentant:: La longueur de l'une des séquences est 0, Donc la longueur de la plus longue sous - séquence commune doit être 0 C'est;
   Les deux autres cas , C'est ce que nous avons mentionné plus haut. a i a_i ai Et b j b_j bj “Équivalence” Avec “Pas égal” Dans les deux cas .Comme le montre la figure, Représente une chaîne “GATCGTGAGC” Et “AGTACG” Pour résoudre la plus longue sous - séquence commune f [ i ] [ j ] ( i , j > 0 ) f[i][j] (i,j > 0) f[i][j](i,j>0) La matrice de.

   Pour les longueurs respectives n n n Et m m m Deux séquences de , En résolvant leurs plus longues sous - séquences communes , Nombre total d'états O ( n m ) O(nm) O(nm) - Oui., La consommation par transfert d'état est O ( 1 ) O(1) O(1),Donc la complexité temporelle totale est O ( n m ) O(nm) O(nm).
  Pour f [ i ] [ j ] f[i][j] f[i][j] Cet état, En cours de résolution ,Dépend uniquement f [ i ] [ j − 1 ] f[i][j-1] f[i][j1] f [ i − 1 ] [ j − 1 ] f[i-1][j-1] f[i1][j1] f [ i − 1 ] [ j ] f[i-1][j] f[i1][j].

Insérer la description de l'image ici
   C'est - à - dire qu'il n'y a qu'une seule solution Ligne précédente Et Cette ligne L'état de , Donc vous pouvez utiliser un tableau de roulement pour l'optimisation , Transformer l'équation de transition d'état en : f [ c u r ] [ j ] = { f [ l a s t ] [ j − 1 ] + 1 j > 0 , a i = b j max ⁡ ( f [ c u r ] [ j − 1 ] , f [ l a s t ] [ j ] ) j > 0 , a i ≠ b j f[cur][j] = \begin{cases}f[last][j-1] + 1 & j>0,a_i=b_j \\ \max(f[cur][j-1], f[last][j]) & j>0,a_i \neq b_j\end{cases} f[cur][j]={ f[last][j1]+1max(f[cur][j1],f[last][j])j>0,ai=bjj>0,ai=bj   Il suffit de mettre i i i Remplacer par c u r cur cur, i − 1 i-1 i1 Remplacer par l a s t last last C'est tout.. C'est comme ça qu'on prend l'original. O ( n m ) O(nm) O(nm) La complexité spatiale de O ( p ) O(p) O(p),Parmi eux p = min ⁡ ( n , m ) p = \min(n,m) p=min(n,m).

  • Optimisé C++ Le Code est implémenté comme suit:
typedef char ValueType;
const int maxn = 5010;
int f[2][maxn];

int getLCSLength(int hsize, ValueType *h, int vsize, ValueType *v) {
    
    memset(f, 0, sizeof(f));
    int cur = 1, last = 0;
    for (int i = 1; i <= vsize; ++i) {
    
        for (int j = 1; j <= hsize; ++j) {
    
            if (v[i] == h[j])
                f[cur][j] = f[last][j - 1] + 1;
            else
                f[cur][j] = max(f[cur][j - 1], f[last][j]);
        }
        swap(last, cur);
    }
    return f[last][hsize];
}

  A propos de La plus longue sous - séquence commune En savoir plus, Vous pouvez vous référer à ce qui suit :.Algorithme d'écriture silencieuse tard dans la nuit(Vingt et un.)- La plus longue sous - séquence commune.

2、 Distance minimale d'édition

  La longueur est n n n Chaîne source pour a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an, Après une certaine opération, la longueur est m m m Chaîne cible pour b 1 , b 2 , . . . b m b_1,b_2,...b_m b1,b2,...bm, Les opérations sont les suivantes: :
  1) I n s e r t Insert Insert: Insérer un caractère dans la chaîne source , La consommation d'insertion est I I I;
  2) D e l e t e Delete Delete: Supprimer un caractère de la chaîne source , Supprimer la consommation D D D;
  3) R e p l a c e Replace Replace: Remplacer un caractère dans la chaîne source par un autre , Remplacer la consommation par R R R;
Réduire au minimum la consommation totale ,Parmi eux n , m ≤ 1000 n,m \le 1000 n,m1000.

  Ordre f [ i ] [ j ] f[i][j] f[i][j] Représente la chaîne source a 1 , a 2 , . . . , a i a_1,a_2,...,a_i a1,a2,...,ai Après les trois opérations ci - dessus, il devient la chaîne de destination b 1 , b 2 , . . . b j b_1,b_2,...b_j b1,b2,...bj Consommation minimale .
  Hypothèses a 1 , a 2 , . . . , a i a_1,a_2,...,a_{i} a1,a2,...,ai Devenir b 1 , b 2 , . . . b j − 1 b_1,b_2,...b_{j-1} b1,b2,...bj1 La consommation minimale de ,égal à f [ i ] [ j − 1 ] f[i][j-1] f[i][j1],Il est nécessaire de a [ i ] a[i] a[i] Insérer un caractère après b j b_j bj, La consommation qui en résulte est: : f [ i ] [ j − 1 ] + I f[i][j-1] + I f[i][j1]+I Comme le montre la figure, La chaîne source est “AGTA”, La chaîne de destination est “GATCGT” Dans le cas de, Changer la chaîne source en "“GATCG” La consommation minimale de f [ i ] [ j − 1 ] f[i][j-1] f[i][j1], Il suffit d'en insérer un autre à la fin de la chaîne source ‘T’, Vous pouvez transformer la chaîne source en chaîne cible “GATCGT”;
Insérer la description de l'image ici
  Hypothèses a 1 , a 2 , . . . , a i − 1 a_1,a_2,...,a_{i-1} a1,a2,...,ai1 Devenir b 1 , b 2 , . . . b j b_1,b_2,...b_{j} b1,b2,...bj La consommation minimale de ,égal à f [ i − 1 ] [ j ] f[i-1][j] f[i1][j],Il faut a i a_i ai Supprimer , La consommation qui en résulte est: : f [ i − 1 ] [ j ] + D f[i-1][j] + D f[i1][j]+D Comme le montre la figure, La chaîne source est “AGTA”, La chaîne de destination est “GATCGT” Dans le cas de,Oui. “AGT” La consommation minimale pour devenir la chaîne cible est de f [ i − 1 ] [ j ] f[i-1][j] f[i1][j], Il suffit de mettre la dernière chaîne source ’A’Supprimer, Vous pouvez transformer la chaîne source en chaîne cible ;

  Hypothèses a 1 , a 2 , . . . , a i − 1 a_1,a_2,...,a_{i-1} a1,a2,...,ai1 Devenir b 1 , b 2 , . . . b j − 1 b_1,b_2,...b_{j-1} b1,b2,...bj1 La consommation minimale de ,égal à f [ i − 1 ] [ j − 1 ] f[i-1][j-1] f[i1][j1],Alors a i a_i ai Remplacer par b j b_j bj, a 1 , a 2 , . . . , a i a_1,a_2,...,a_{i} a1,a2,...,ai Peut devenir b 1 , b 2 , . . . b j b_1,b_2,...b_{j} b1,b2,...bj. Remplacement à prendre en considération a i = b j a_i=b_j ai=bj Et a i ≠ b j a_i \neq b_j ai=bj Situation, La consommation résultant du remplacement est donc : f [ i − 1 ] [ j − 1 ] + { 0 a i = b j R a i ≠ b j f[i-1][j-1] + \begin{cases} 0 & a_i=b_j \\ R & a_i \neq b_j\end{cases} f[i1][j1]+{ 0Rai=bjai=bj Comme le montre la figure, La chaîne source est “AGTA”, La chaîne de destination est “GATCGT” Dans le cas de,Oui. “AGT” Devenir “GATCGT” La consommation minimale de f [ i − 1 ] [ j − 1 ] f[i-1][j-1] f[i1][j1], Alors, tant que Chaîne source Dernier caractère de Remplacer par: Chaîne de destination Dernier caractère de , Vous pouvez transformer la chaîne source en chaîne cible ; Remplacer par Chaîne source Et Chaîne de destination Est égal ou non à l'origine pour déterminer la consommation ;

  • Les conditions limites sont les suivantes: :
      a. La chaîne vide devient la chaîne cible C'est - à - dire: f [ 0 ] [ j ] f[0][j] f[0][j], Total à insérer j j j Caractères,Alors... f [ 0 ] [ j ] = f [ 0 ] [ j − 1 ] + I f[0][j] = f[0][j-1] + I f[0][j]=f[0][j1]+I;
      b. La chaîne source devient vide C'est - à - dire: f [ i ] [ 0 ] f[i][0] f[i][0], Total à supprimer i i i Caractères,Alors... f [ i ] [ 0 ] = f [ i − 1 ] [ 0 ] + D f[i][0] = f[i-1][0] + D f[i][0]=f[i1][0]+D;
      c. Une chaîne vide devient une chaîne vide C'est - à - dire: f [ 0 ] [ 0 ] = 0 f[0][0] = 0 f[0][0]=0

   Consolider tous les états ci - dessus , L'équation de transfert d'état est obtenue comme suit: : f [ i ] [ j ] = { 0 i = 0 , j = 0 f [ i ] [ j − 1 ] + I i = 0 , j > 0 f [ i − 1 ] [ j ] + D i > 0 , j = 0 min ⁡ i > 0 , j > 0 { f [ i ] [ j − 1 ] + I f [ i − 1 ] [ j ] + D f [ i − 1 ] [ j − 1 ] + R a i ≠ b j f[i][j] = \begin{cases}0 & i=0,j=0\\f[i][j-1]+I & i=0,j>0\\ f[i-1][j] + D & i>0,j=0 \\ \min_{i>0,j>0} \begin{cases} f[i][j-1] + I\\ f[i-1][j] + D\\ f[i-1][j-1] + R_{a_i \neq b_j}\end{cases}\end{cases} f[i][j]=0f[i][j1]+If[i1][j]+Dmini>0,j>0f[i][j1]+If[i1][j]+Df[i1][j1]+Rai=bji=0,j=0i=0,j>0i>0,j=0
   Par cette matrice d'état , Enfin calculé f [ n ] [ m ] f[n][m] f[n][m] C'est ce qu'on demande. "Chaîne source a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an,Passe. Insérer、Supprimer、Remplacer Devient la chaîne de destination b 1 , b 2 , . . . b m b_1,b_2,...b_m b1,b2,...bm" Consommation minimale ,Spécial,Quand I = D = R = 1 I = D = R = 1 I=D=R=1 Heure, f [ n ] [ m ] f[n][m] f[n][m] C'est une chaîne. a a a Et b b b Distance levinstein de .
   Nombre total d & apos; États O ( n m ) O(nm) O(nm), La consommation par transfert d'état est O ( 1 ) O(1) O(1),Donc la complexité temporelle totale est O ( n m ) O(nm) O(nm), L'espace peut être optimisé avec un tableau de roulement , Le schéma d'optimisation spécifique peut être référencé La plus longue sous - séquence commune Processus de résolution de .
   La figure montre une chaîne source “AGTACG” à la chaîne de destination “GATCGTGAGC” Diagramme de distance levinstein pour .
Insérer la description de l'image ici
   En savoir plus sur la distance minimale d'édition ,Peut être référencé:.Algorithme d'écriture silencieuse tard dans la nuit(Vingt - deux.)- Distance minimale d'édition .

3、 Problème d'appariement à double chaîne

  Compte tenu d'un Chaîne correspondante s ( Ne contient que des lettres minuscules ) Et un Chaîne de motif p ( Contient des lettres minuscules et deux caractères supplémentaires :'.'Et '*'), Nécessite un soutien '.'Et '*' Expression régulière correspondant à ('*' Caractères garantis devant ).
  '.'Correspond à n'importe quel caractère individuel
  '*' Correspond à l'élément précédent de zéro ou plus

   C'est un classique. Correspondance des chaînes Questions,Peut suivre La plus longue sous - séquence commune Pour trouver une solution .Ordre f ( i , j ) f(i, j) f(i,j) Représentant: Préfixe de chaîne correspondant s[0:i] Et Préfixe de chaîne de mode p[0:j] Y a - t - il une correspondance? ,Il n'y a que deux valeurs: 0 Représentant Ne correspond pas, 1 Représentant Ça correspond.
  Et donc,, Discussion sur les chaînes de mode :
  1)Quand p[j] Pour.Heure,Représentant s[i] Lorsque n'importe quel caractère , Ça correspond. (Ça va aller??Pas de problème.), Donc la question se transforme en une demande Préfixe de chaîne correspondant s[0:i-1] Et Préfixe de chaîne de mode p[0:j-1] Y a - t - il un problème de correspondance? , C'est le cas. f ( i , j ) = f ( i − 1 , j − 1 ) f(i, j) = f(i-1, j-1) f(i,j)=f(i1,j1),Comme le montre la figure1Comme indiqué:


  2)Quand p[j] Pour*Heure,Parce que* Caractères garantis devant , Donc j'ai les caractères. p[j-1],Discussion de cas:
    2.a)Si p[j-1] Pour.Heure, Peut correspondre à tous s[0:i] Suffixe pour,Dans ce cas,Tant que f ( k , j − 2 ) f(k, j-2) f(k,j2) Pour 1, f ( i , j ) f(i, j) f(i,j) C'est tout. 1;Parmi eux k ∈ [ 0 , i ] k \in [0, i] k[0,i].Comme le montre la figure ci - dessous:


    2.b)Si p[j-1] Non.Heure,Seulement si s[0:i] Suffixe pour Tous les caractères sont p[j-1] Heure, Pour correspondre s[0:i] Préfixe, Se transforme également en f ( k , j − 2 ) f(k, j-2) f(k,j2) Sous - Questions .Comme le montre la figure ci - dessous:


  3)Quand p[j] Tout autre caractère ,Une fois p[j] Et s[i] Ne correspond pas,C'est tout. f ( i , j ) = 0 f(i, j) = 0 f(i,j)=0,Sinon f ( i , j ) = f ( i − 1 , j − 1 ) f(i, j) = f(i-1, j-1) f(i,j)=f(i1,j1),Comme le montre la figure ci - dessous:


  Enfin, Cette question peut être utilisée Recherche de mémoire Résoudre, Et certaines conditions limites doivent être prises en considération , Les conditions limites peuvent être expliquées dans la mise en œuvre du Code. . La recherche de mémoire sera examinée plus en détail ci - dessous. .
   La longueur de la chaîne correspondante est n n n, La longueur de la chaîne de mode est m m m. Nombre de pays : O ( n m ) O(nm) O(nm),Changement d'état: O ( n ) O(n) O(n),Complexité temporelle: O ( n 2 m ) O(n^2m) O(n2m).

Quatre、Recherche de mémoire

  Compte tenu d'un n ( n ≤ 45 ) n(n \le 45) n(n45),S'il te plaît. Numéro de la série Fibonacci n n n Valeur de l'élément, Nécessite une mise en œuvre récursive .

  Alors, Il suffit d'appliquer la fonction récursive ci - dessus , Et gérer la sortie récursive , Peut être écrit Récursivement ,CLangues Le Code est implémenté comme suit:

int f(unsigned int n) {
    
    if(n <= 1) {
    
        return 1;
    }
    return f(n-1) + f(n-2);
}

   Le processus de résolution récursive est le suivant: :

   C'est un arbre binaire. ,La hauteur de l'arbre est n n n, Donc le nombre de noeuds dans l'accès récursif est 2 n 2^n 2n, Mais regardez attentivement , Pour n'importe quel sous - arbre , La hauteur du sous - arbre gauche doit être supérieure à celle du sous - arbre droit. , Donc ce n'est pas un arbre strictement binaire . Pour explorer sa complexité temporelle réelle ,Changeons le Code.:

int f(unsigned int n) {
    
    ++c[n];
    if(n <= 1) {
    
        return 1;
    }
    return f(n-1) + f(n-2);
}

   Ajouter un code ++c[n];, Introduire un compteur , Regardez - moi ça. n n n Dans le cas de, f ( n ) f(n) f(n) Nombre d'appels à cette fonction ,Comme le montre la figure:
Insérer la description de l'image ici
  Observation c [ n ] c[n] c[n] Tendances de la croissance , Exclure d'abord les séquences équidistantes , Ensuite, nous verrons s'il y a une séquence de nombres proportionnels , Essayons de trouver. c [ n ] / c [ n − 1 ] c[n] / c[n-1] c[n]/c[n1] Valeur de, Les tableaux suivants sont énumérés: :
Insérer la description de l'image ici
  Observations,Avec n n n De plus en plus, c [ n ] / c [ n − 1 ] c[n]/c[n-1] c[n]/c[n1] De plus en plus près d'une constante , Et cette constante est l'inverse de la partition d'or : 2 5 − 1 ≈ 1.618034 \frac {2}{ \sqrt 5 - 1} \approx 1.618034 5 121.618034  Quand n n n Vers l'infini , Satisfaire à la formule suivante: : c [ n ] = 2 5 − 1 c [ n − 1 ] c[n] = \frac {2}{ \sqrt 5 - 1} c[n-1] c[n]=5 12c[n1]   La multiplication cumulative est obtenue en résolvant une série de rapports égaux : c [ n ] = 2 5 − 1 c [ n − 1 ] = ( 2 5 − 1 ) 2 c [ n − 2 ] = ( 2 5 − 1 ) n \begin{aligned}c[n] &= \frac {2}{ \sqrt 5 - 1} c[n-1]\\ &= (\frac {2}{ \sqrt 5 - 1})^2 c[n-2]\\ &= (\frac {2}{ \sqrt 5 - 1})^n \end{aligned} c[n]=5 12c[n1]=(5 12)2c[n2]=(5 12)n  Alors..., La complexité temporelle de la solution récursive des séries Fibonacci est : O ( ( 2 5 − 1 ) n ) O((\frac {2}{ \sqrt 5 - 1})^n) O((5 12)n)
   C'est un algorithme exponentiel ,Avec n n n De plus en plus, La consommation de temps augmente de façon exponentielle , Nous devons éviter d'écrire du Code comme ça. , Surtout pendant le développement du serveur ,CPU Est une ressource extrêmement précieuse , Tout gaspillage est honteux. .Mais, L'intervieweur a demandé une mise en oeuvre récursive , C'est vraiment ennuyeux. !
  Alors, Comment optimiser la consommation de puissance de calcul ici ?
   La résolution récursive des séquences Fibonacci est en fait un processus de recherche en profondeur , C'est une énumération non optimisée de la violence ,Pour f ( 5 ) f(5) f(5) Résolution de,Comme le montre la figure:

  En même temps,On a aussi trouvé, Il y a beaucoup de sous - problèmes qui se chevauchent dans le calcul ,Par exemple f ( 3 ) f(3) f(3) C'est calculé. 2 2 2 Une fois,Comme le montre la figure:

   f ( 2 ) f(2) f(2) C'est calculé. 3 3 3 Une fois,Comme le montre la figure:
Insérer la description de l'image ici
   Donc si nous pouvons nous assurer que chaque f ( i ) f(i) f(i) Il n'est calculé qu'une seule fois,Le problème est résolu. On pourrait envisager f ( i ) f(i) f(i) Les valeurs calculées sont stockées dans un tableau de hachage h [ i ] h[i] h[i] Moyenne, Lors de la deuxième visite f ( i ) f(i) f(i) Heure,Prenez directement h [ i ] h[i] h[i] La valeur de, Donc chaque fois que vous Calculez f ( i ) f(i) f(i) La complexité temporelle de O ( 1 ) O(1) O(1), Total à calculer f ( 2 ) , f ( 3 ) , . . . f ( n ) f(2),f(3),...f(n) f(2),f(3),...f(n),La complexité temporelle totale devient O ( n ) O(n) O(n) .
   Ce type de tableau de hachage est utilisé pour enregistrer les résultats de l'opération , La façon d'éviter les opérations répétitives est de mémoriser la recherche .
   Comment cela se passe - t - il? ?
   Nous utilisons un tableau h [ i ] h[i] h[i] Pour enregistrer Série Fibonacci No i i i Valeur de l'élément, Modifier le Code récursif précédent comme suit: :

const int inf = -1;
int h[46];

void init() {
    
    memset(h, inf, sizeof(h));  // 1)
}

int f(unsigned int n) {
    
    if(n <= 1) {
    
        return 1;
    }
    int &fib = h[n];            // 2)
    if(fib != inf) {
    
        return fib;             // 3)
    }
    fib = f(n-1) + f(n-2);      // 4)
    return fib;
}
  • 1) Initialiser tous f ( i ) f(i) f(i) Aucun n'a été calculé. , Pour plus de commodité memset,Vous pouvez infDéfinition -1;
  • 2) Notez qu'il y a une référence ici , Et assurez - vous d'utiliser des références , Laisser les lecteurs réfléchir à des raisons spécifiques , Bien sûr que non. , Comme indiqué ci - dessous , Ne t'inquiète pas. ;
  • 3)Quand fibC'est - à - dire h[n] C'est calculé. , Renvoie le résultat directement ;
  • 4)Enfin, Calcul récursif h[n]Valeur de, Et renvoie le résultat ;

   Par rapport à la version récursive , Il y a tellement de code. :

    int &fib = h[n];
    if(fib != inf) {
    
        return fib;
    }

   Alors où est - ce que ça marche? ? Nous le sentons à travers une carte en mouvement :

  Comme le montre la figure, Lorsque le deuxième calcul est nécessaire f ( 2 ) f(2) f(2) Et f ( 3 ) f(3) f(3) Heure, Parce que les résultats ont été calculés et stockés dans h [ 2 ] h[2] h[2] Et h [ 3 ] h[3] h[3] Moyenne, Donc le code ci - dessus fib != inf L'expression est vraie ,Retour direct, Le calcul récursif vers le bas n'est plus nécessaire , C'est comme ça qu'on prend l'original. “ Arbre binaire récursif ” Converti en “ Chaîne récursive ”, Ainsi, l'algorithme exponentiel original devient un niveau polynomial .
   La méthode de réalisation de la recherche de mémoire a été expliquée par un exemple simple ci - dessus. , En outre, l'utilisation d'un tableau pour enregistrer les sous - problèmes de chevauchement calculés est mentionnée. , C'est très similaire à l'idée de programmation dynamique ,C'est vrai, La recherche de mémoire est en fait une idée de programmation dynamique . Pour être plus précis, , Peut être représenté par la formule suivante: :

Recherche de mémoire = Réalisation d'une recherche approfondie en priorité + Idées de programmation dynamique

   En savoir plus sur la recherche de mémoire ,Peut être référencé: .Algorithme d'écriture silencieuse tard dans la nuit(Vingt - six.)- Recherche de mémoire.

Cinq、Problème de sac à dos

1、0/1 Sac à dos

  Oui. n ( n ≤ 100 ) n(n \le100) n(n100) Articles et une capacité de m ( m ≤ 10000 ) m(m \le 10000) m(m10000) Sac à dos.No i i i La capacité de chaque article est c [ i ] c[i] c[i], La valeur est w [ i ] w[i] w[i]. Vous devez maintenant choisir des articles à mettre dans votre sac à dos , Et la capacité totale ne doit pas dépasser la capacité du sac à dos , Trouver la valeur totale maximale de l'article qui peut être atteint .

  C'est tout ce qui précède. 0/1 Description complète du problème du sac à dos ,Pourquoi? 0/1 Sac à dos, Parce qu'il n'y en a qu'un par article. , Vous pouvez choisir de mettre votre sac à dos ou non ,Et 0 Ça ne veut rien dire. ,1 Delegate Release .
  Première étape: État de la conception ;
  Statut ( i , j ) (i, j) (i,j) Indique avant i i i Les articles sont placés exactement dans la capacité j j j Sac à dos ( i ∈ [ 0 , n ] , j ∈ [ 0 , m ] ) (i \in [0, n], j \in [0, m]) (i[0,n],j[0,m]);
  Ordre d p [ i ] [ j ] dp[i][j] dp[i][j] État de la représentation ( i , j ) (i, j) (i,j) Valeur maximale du sac à dos , Avant i i i Les articles sont placés exactement dans la capacité j j j Valeur totale maximale du sac à dos ;
  Deuxième étape: Liste des équations de transfert d'état ; d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − c [ i ] ] + w [ i ] ) dp[i][j] = max(dp[i-1][j], dp[i-1][j - c[i]] + w[i]) dp[i][j]=max(dp[i1][j],dp[i1][jc[i]]+w[i]) Parce que chaque article ,Ou pas., Il suffit donc d'examiner les points suivants: i i i Article (s) Pose ça. Ou Non. Situation:
  1)Non.:Si “No i i i Les articles ne sont pas placés dans une capacité de j j j Sac à dos”, Alors le problème se traduit par “Avant i − 1 i-1 i1 Articles placés dans une capacité de j j j Sac à dos” La question de; Parce qu'il n'y a pas de place , Donc la valeur maximale est égale à “Avant i − 1 i-1 i1 Articles placés dans une capacité de j j j Sac à dos” Valeur maximale ,C'est - à - dire: d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j];
  2)Pose ça.:Si “No i i i Articles placés dans une capacité de j j j Sac à dos”, Alors le problème se traduit par “Avant i − 1 i-1 i1 Articles placés dans une capacité de j − c [ i ] j-c[i] jc[i] Sac à dos” La question de; Alors la valeur maximale est égale à “Avant i − 1 i-1 i1 Articles placés dans une capacité de j − c [ i ] j-c[i] jc[i] Sac à dos” Valeur maximale Ajouter le paragraphe suivant: i i i Valeur des articles ,C'est - à - dire: d p [ i − 1 ] [ j − c [ i ] ] + w [ i ] dp[i-1][j - c[i]] + w[i] dp[i1][jc[i]]+w[i];
   La plus élevée des deux valeurs suivantes: , C'est ce qu'on demande. “Avant i i i Les articles sont placés exactement dans la capacité j j j Sac à dos” La plus grande valeur de .
  Nous avons découvert, Lorsque l'état est en transition , ( i , j ) (i, j) (i,j) Pas du tout. ( i − 1 , j ) (i-1, j) (i1,j), C'est de ( i − 1 , j − c [ i ] ) (i-1, j - c[i]) (i1,jc[i]), Il doit donc y avoir un état initial , Et cet état initial est ( 0 , 0 ) (0, 0) (0,0),Ça veut dire: “Avant 0 Les articles sont placés dans un sac à dos d'une capacité de 0 Sac à dos”, La valeur maximale dans cet état est 0,C'est - à - dire: d p [ 0 ] [ 0 ] = 0 dp[0][0] = 0 dp[0][0]=0;
   On y réfléchira. , ( 0 , 3 ) (0, 3) (0,3) Qu'est - ce que ça veut dire?? Il représente “Avant 0 Les articles sont placés dans un sac à dos d'une capacité de 3 Sac à dos”, Il est clair que cela n'existe pas. ,Parce que 0 La valeur d'un article doit être 0. C'est ce qu'on appelle un état illégal. , L'état illégal ne peut pas être transféré , Ainsi, nous pouvons initialiser tous les états par l'état initial et l'état illégal .
   d p [ 0 ] [ i ] = { 0 i = 0 i n f i > 0 dp[0][i] = \begin{cases} 0 & i = 0\\ inf & i > 0\end{cases} dp[0][i]={ 0infi=0i>0
  Parmi eux i n f inf inf Lors de la mise en œuvre du programme , Nous pouvons définir un très petit nombre ,Par exemple, − 1000000000 -1000000000 1000000000, Il ne peut pas être un candidat à la solution optimale tant qu'il est garanti qu'il n'y a pas de transition d'état. . Pour approfondir le concept de transition d'état , Regardez la figure 2. -5-1 Un exemple, Chaque grille représente un état , ( 0 , 0 ) (0,0) (0,0) Représente l'état initial , La grille bleue représente l'état obtenu , La grille grise représente un état illégal , La grille rouge représente l'état du transfert en cours , Dans la figure i i i Oui, c'est avant. i i i Valeur optimale de la capacité de chaque article ,No 4 La capacité des articles est 2,Valeur: 8, Les transferts d'état sont les suivants: : d p [ 4 ] [ 4 ] = m a x ( d p [ 4 − 1 ] [ 4 ] , d p [ 4 − 1 ] [ 4 − 2 ] + 8 ) = m a x ( d p [ 3 ] [ 4 ] , d p [ 3 ] [ 2 ] + 8 ) \begin{aligned} dp[4][4] &= max( dp[4-1][4], dp[4-1][4 - 2] + 8) \\ &= max( dp[3][4], dp[3][2] + 8) \end{aligned} dp[4][4]=max(dp[41][4],dp[41][42]+8)=max(dp[3][4],dp[3][2]+8)

  Concernant 0/1 Plus d'informations sur le sac à dos ,Peut être référencé:.Algorithme d'écriture silencieuse tard dans la nuit(XIV.)- 0/1 Sac à dos.

2、Sac à dos complet

  Oui. n ( n ≤ 100 ) n(n \le 100) n(n100) Et une capacité de m ( m ≤ 10000 ) m(m \le 10000) m(m10000) Sac à dos.No i i i La capacité de l'article est c [ i ] c[i] c[i], La valeur est w [ i ] w[i] w[i]. Vous devez maintenant choisir des articles à mettre dans votre sac à dos , Choix illimité pour chaque article , Et la capacité totale ne doit pas dépasser la capacité du sac à dos , Trouver la valeur totale maximale de l'article qui peut être atteint .

   Voici une description complète du problème du sac à dos complet ,Et 0/1 La différence entre les sacs à dos est que chaque article peut être sélectionné à l'infini , C'est - à - dire le contenu de la police rouge dans le texte ;
  Première étape: État de la conception ;
  Statut ( i , j ) (i, j) (i,j) Indique avant i i i Les articles sont placés exactement dans la capacité j j j Sac à dos ( i ∈ [ 0 , n ] , j ∈ [ 0 , m ] ) (i \in [0, n], j \in [0, m]) (i[0,n],j[0,m]);
  Ordre d p [ i ] [ j ] dp[i][j] dp[i][j] État de la représentation ( i , j ) (i, j) (i,j) Valeur maximale du sac à dos , Avant i i i Article (s) ( Nombre illimité de pièces disponibles pour chaque article ) Juste dans la capacité de j j j Valeur totale maximale du sac à dos ;

  Deuxième étape: Liste des équations de transfert d'état ; d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j − c [ i ] ∗ k ] + w [ i ] ∗ k ) dp[i][j] = max(dp[i-1][j - c[i]*k] + w[i]*k) dp[i][j]=max(dp[i1][jc[i]k]+w[i]k) ( 0 ≤ k ≤ j c [ i ] ) (0 \le k \le \frac {j} {c[i]}) (0kc[i]j)

  • Parce qu'il y a une infinité d'options pour chaque article , Il est classé comme suit: :
      1)Non.:Si “No i i i Les articles ne sont pas placés dans la capacité j j j Sac à dos”, Alors le problème se traduit par “Avant i − 1 i-1 i1 Capacité de mise en place des articles j j j Sac à dos” La question de; Parce qu'il n'y a pas de place , Donc la valeur maximale est égale à “Avant i − 1 i-1 i1 Capacité de mise en place des articles j j j Sac à dos” Valeur maximale , Dans l'équation de transfert d'état correspondante k = 0 k = 0 k=0 Situation, C'est - à - dire: d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j];
      2)Pose ça. k - Oui.:Si “No i i i Capacité de mise en place des articles j j j Sac à dos”, Alors le problème se traduit par “Avant i − 1 i-1 i1 Capacité de mise en place des articles j − c [ i ] ∗ k j-c[i]*k jc[i]k Sac à dos” La question de; Alors la valeur maximale est égale à “Avant i − 1 i-1 i1 Capacité de mise en place des articles j − c [ i ] ∗ k j-c[i]*k jc[i]k Sac à dos” Valeur maximale Ajouter k k k No. i i i Valeur des espèces ,C'est - à - dire: d p [ i − 1 ] [ j − c [ i ] ∗ k ] + w [ i ] ∗ k dp[i-1][j - c[i]*k] + w[i]*k dp[i1][jc[i]k]+w[i]k;
       Énumérer tous ceux qui remplissent les conditions k k k C'est ce qu'on demande. “Avant i i i Les articles sont placés exactement dans la capacité j j j Sac à dos” La plus grande valeur de .Attention!: Parce que chaque article a un choix illimité , C'est pour ça qu'on les décrit ici. “Espèce” En unités, Représente différents types d'articles .

  Pour n n n Mettre l'article dans une capacité de m m m Sac à dos, Le nombre d'états est O ( n m ) O(nm) O(nm), La consommation par transfert d'état est O ( k ) O(k) O(k), La complexité temporelle de l'ensemble du processus de transition de l'état est donc supérieure à O ( n m ) O(nm) O(nm) De, Qu'est - ce que c'est? ? Envisager le pire scénario ,C'est - à - dire: c [ i ] = 1 c[i] = 1 c[i]=1 Heure, Alors, calculez. d p [ i ] [ j ] dp[i][j] dp[i][j] Le nombre de transferts pour j j j, Le nombre total de transitions d'état est m ( m + 1 ) 2 \frac {m(m + 1)} {2} 2m(m+1), Donc la complexité temporelle de l'algorithme est O ( n m 2 ) O(nm^2) O(nm2) De, C'est - à - dire que la complexité du temps d'étalement moyen du transfert d'état est O ( m ) O(m) O(m) De.

   Nous développons l'équation de transfert d'état et obtenons ce qui suit: k + 1 k+1 k+1 Formule :
d p [ i ] [ j ] = m a x { d p [ i − 1 ] [ j ] ( 1 ) d p [ i − 1 ] [ j − c [ i ] ] + w [ i ] ( 2 ) d p [ i − 1 ] [ j − c [ i ] ∗ 2 ] + w [ i ] ∗ 2 ( 3 ) . . . d p [ i − 1 ] [ j − c [ i ] ∗ k ] + w [ i ] ∗ k ( k + 1 ) dp[i][j] = max \begin{cases} dp[i-1][j] & (1)\\ dp[i-1][j - c[i]] + w[i] & (2)\\ dp[i-1][j - c[i]*2] + w[i]*2 & (3)\\ ... \\ dp[i-1][j - c[i]*k] + w[i] *k & (k+1) \end{cases} dp[i][j]=maxdp[i1][j]dp[i1][jc[i]]+w[i]dp[i1][jc[i]2]+w[i]2...dp[i1][jc[i]k]+w[i]k(1)(2)(3)(k+1)
   Utiliser la méthode du coefficient indéterminé ,Avec j − c [ i ] j-c[i] jc[i] Au lieu de la formule ci - dessus j j j On obtient la formule suivante: :
d p [ i ] [ j − c [ i ] ] = m a x { d p [ i − 1 ] [ j − c [ i ] ] ( 1 ) d p [ i − 1 ] [ j − c [ i ] ∗ 2 ] + w [ i ] ( 2 ) d p [ i − 1 ] [ j − c [ i ] ∗ 3 ] + w [ i ] ∗ 2 ( 3 ) . . . d p [ i − 1 ] [ j − c [ i ] ∗ k ] + w [ i ] ∗ ( k − 1 ) ( k ) dp[i][j-c[i]] = max \begin{cases} dp[i-1][j-c[i]] & (1)\\ dp[i-1][j - c[i]*2] + w[i] & (2)\\ dp[i-1][j - c[i]*3] + w[i]*2 & (3)\\ ... \\ dp[i-1][j - c[i]*k] + w[i] *(k-1) & (k) \end{cases} dp[i][jc[i]]=maxdp[i1][jc[i]]dp[i1][jc[i]2]+w[i]dp[i1][jc[i]3]+w[i]2...dp[i1][jc[i]k]+w[i](k1)(1)(2)(3)(k)
   Ajouter les deux côtés de l'équation w [ i ] w[i] w[i] Je l'ai.:
d p [ i ] [ j − c [ i ] ] + w [ i ] = m a x { d p [ i − 1 ] [ j − c [ i ] ] + w [ i ] ( 1 ) d p [ i − 1 ] [ j − c [ i ] ∗ 2 ] + w [ i ] ∗ 2 ( 2 ) d p [ i − 1 ] [ j − c [ i ] ∗ 3 ] + w [ i ] ∗ 3 ( 3 ) . . . d p [ i − 1 ] [ j − c [ i ] ∗ k ] + w [ i ] ∗ k ( k ) dp[i][j-c[i]] + w[i] = max \begin{cases} dp[i-1][j-c[i]] + w[i] & (1)\\ dp[i-1][j - c[i]*2] + w[i]*2 & (2)\\ dp[i-1][j - c[i]*3] + w[i]*3 & (3)\\ ... \\ dp[i-1][j - c[i]*k] + w[i] *k & (k) \end{cases} dp[i][jc[i]]+w[i]=maxdp[i1][jc[i]]+w[i]dp[i1][jc[i]2]+w[i]2dp[i1][jc[i]3]+w[i]3...dp[i1][jc[i]k]+w[i]k(1)(2)(3)(k)
   Et nous avons découvert ,Ici. ( 1 ) . . . ( k ) (1)...(k) (1)...(k) Équation équivalente à l'équation de transition d'état initiale ( 2 ) . . . ( k + 1 ) (2) ... (k+1) (2)...(k+1) Équation, Par conséquent, l'équation de transfert d'état originale peut être simplifiée comme suit: : d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − c [ i ] ] + w [ i ] ) dp[i][j] = max(dp[i-1][j], dp[i][j-c[i]] + w[i]) dp[i][j]=max(dp[i1][j],dp[i][jc[i]]+w[i])
   De cette façon, la complexité du temps de partage initial est O ( m ) O(m) O(m) Le transfert d'état est optimisé pour O ( 1 ) O(1) O(1).
   Donc nous allons comprendre ce que signifie cette équation de transition d'état :Pour la section i i i Article (s) , Il n'y a que deux options. : Pas un seul. 、 Au moins un. ; Pas un seul. C'est “Avant i − 1 i-1 i1 Pour remplir un article d'une capacité de j j j Sac à dos” Situation,C'est - à - dire: d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j]; Au moins un. Et si, Nous avons essayé “Avant i i i Pour remplir un article d'une capacité de j j j Sac à dos” Enlève ça. 1 Article (s),C'est - à - dire: “Avant i i i Pour remplir un article d'une capacité de j − c [ i ] j-c[i] jc[i] Sac à dos”, La valeur est d p [ i ] [ j − c [ i ] ] + w [ i ] dp[i][j-c[i]] + w[i] dp[i][jc[i]]+w[i]. Le plus grand des deux est la réponse. .
   En fait, je peux commencer cet article , Facile à comprendre , Le processus d'optimisation et de dérivation progressive est introduit , J'essaie de le dire au lecteur. , De nombreux problèmes de programmation dynamique ne peuvent pas être appliqués aux modèles , Partir d'une idée simple , Plus quelques déductions et Optimisations , Résoudre les problèmes complexes étape par étape , C'est la pensée universelle pour résoudre les problèmes .
   En savoir plus sur le sac à dos complet ,Peut être référencé:.Algorithme d'écriture silencieuse tard dans la nuit(Quinze.)- Sac à dos complet.

3、 Sac à dos multiple

  Oui. n ( n ≤ 100 ) n(n \le 100) n(n100) Et une capacité de m ( m ≤ 10000 ) m(m \le 10000) m(m10000) Sac à dos.No i i i La capacité de l'article est c [ i ] c[i] c[i], La valeur est w [ i ] w[i] w[i]. Vous devez maintenant choisir des articles à mettre dans votre sac à dos , Chaque article peut être sélectionné x [ i ] x[i] x[i] Pièce (s), Et la capacité totale ne doit pas dépasser la capacité du sac à dos , Trouver la valeur totale maximale de l'article qui peut être atteint .

   Voici une description complète du problème des sacs à dos multiples ,Et 0/1 Sac à dos、 La différence entre un sac à dos complet et un sac à dos complet est que le choix de chaque article a ses propres limites de plage. , C'est - à - dire le contenu de la police rouge dans le texte ;
  Première étape: État de la conception ;
  Statut ( i , j ) (i, j) (i,j) Indique avant i i i Les articles sont placés exactement dans la capacité j j j Sac à dos ( i ∈ [ 0 , n ] , j ∈ [ 0 , m ] ) (i \in [0, n], j \in [0, m]) (i[0,n],j[0,m]);
  Ordre d p [ i ] [ j ] dp[i][j] dp[i][j] État de la représentation ( i , j ) (i, j) (i,j) Valeur maximale du sac à dos , Avant i i i Article (s) ( Chaque article peut être sélectionné x [ i ] x[i] x[i] Pièce (s)) Juste dans la capacité de j j j Valeur totale maximale du sac à dos ;

  Deuxième étape: Liste des équations de transfert d'état ; d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j − c [ i ] ∗ k ] + w [ i ] ∗ k ) ( 0 ≤ k ≤ x [ i ] ) dp[i][j] = max(dp[i-1][j - c[i]*k] + w[i]*k) \\ (0 \le k \le x[i]) dp[i][j]=max(dp[i1][jc[i]k]+w[i]k)(0kx[i]) Parce que chaque article a x [ i ] x[i] x[i] Plantable , Il est classé comme suit: :
  1)Non.:Si “No i i i Les articles ne sont pas placés dans la capacité j j j Sac à dos”, Alors le problème se traduit par “Avant i − 1 i-1 i1 Capacité de mise en place des articles j j j Sac à dos” La question de; Parce qu'il n'y a pas de place , Donc la valeur maximale est égale à “Avant i − 1 i-1 i1 Capacité de mise en place des articles j j j Sac à dos” Valeur maximale , Dans l'équation de transfert d'état correspondante k = 0 k = 0 k=0 Situation, C'est - à - dire: d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j];
  2)Pose ça. k - Oui.:Si “No i i i Capacité de mise en place des articles j j j Sac à dos”, Alors le problème se traduit par “Avant i − 1 i-1 i1 Capacité de mise en place des articles j − c [ i ] ∗ k j-c[i]*k jc[i]k Sac à dos” La question de; Alors la valeur maximale est égale à “Avant i − 1 i-1 i1 Capacité de mise en place des articles j − c [ i ] ∗ k j-c[i]*k jc[i]k Sac à dos” Valeur maximale Ajouter k k k No. i i i Valeur des espèces ,C'est - à - dire: d p [ i − 1 ] [ j − c [ i ] ∗ k ] + w [ i ] ∗ k dp[i-1][j - c[i]*k] + w[i]*k dp[i1][jc[i]k]+w[i]k;
   Énumérer tous ceux qui remplissent les conditions k k k C'est ce qu'on demande. “Avant i i i Les articles sont placés exactement dans la capacité j j j Sac à dos” La plus grande valeur de .
   Le problème du sac à dos multiple est le cas général du problème du sac à dos , Chaque article a ses propres limites de plage . Si vous commencez par l'équation de transfert d'état , Nous pouvons résumer et unifier trois types de problèmes de sac à dos , On obtient une équation unifiée de transfert d'état comme suit: : d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j − c [ i ] ∗ k ] + w [ i ] ∗ k ) dp[i][j] = max(dp[i-1][j - c[i]*k] + w[i]*k) dp[i][j]=max(dp[i1][jc[i]k]+w[i]k)  Pour 0/1 Problème de sac à dos, k k k La valeur de 0 , 1 0,1 0,1;
   Pour les problèmes de sac à dos complet , k k k La valeur de 0 , 1 , 2 , 3 , . . . , ⌊ j c [ i ] ⌋ 0, 1, 2, 3, ..., \lfloor \frac j {c[i]} \rfloor 0,1,2,3,...,c[i]j;
   Pour les problèmes de sac à dos multiple , k k k La valeur de 0 , 1 , 2 , 3 , . . . , x [ i ] 0, 1, 2, 3, ..., x[i] 0,1,2,3,...,x[i];
  Pour n n n Mettre l'article dans une capacité de m m m Sac à dos, Le nombre d'états est O ( n m ) O(nm) O(nm), La consommation par transfert d'état est O ( x [ i ] ) O(x[i]) O(x[i]), La complexité temporelle de l'ensemble du processus de transition de l'état est donc supérieure à O ( n m ) O(nm) O(nm) De, Qu'est - ce que c'est? ?
   Envisager le pire scénario ,C'est - à - dire: x [ i ] = m x[i] = m x[i]=m Heure, Alors, calculez. d p [ i ] [ j ] dp[i][j] dp[i][j] Le nombre de transferts pour j j j, Le nombre total de transitions d'état est m ( m + 1 ) 2 \frac {m(m + 1)} {2} 2m(m+1), Donc la complexité temporelle de l'algorithme est O ( n m 2 ) O(nm^2) O(nm2) De, C'est - à - dire que la complexité du temps d'étalement moyen du transfert d'état est O ( m ) O(m) O(m) De.
   Une optimisation facile à imaginer est : Nous pouvons diviser chaque article en x [ i ] x[i] x[i] - Oui., C'est devenu ∑ i = 1 n x [ i ] \sum_{i=1}^n x[i] i=1nx[i] Articles 0/1 Problème de sac à dos,Nous savons que 0/1 Après optimisation des problèmes de sac à dos , La complexité spatiale n'est liée qu'à la capacité ,C'est - à - dire: O ( m ) O(m) O(m).
   Ainsi, la complexité spatiale des problèmes de sac à dos multiple peut au moins être optimisée O ( m ) O(m) O(m) De.
  Et pourtant, Si vous divisez ainsi , La complexité temporelle n'a pas changé. , Mais ça nous donne une idée. , C'est que chaque objet est séparable. .Supposons qu'il y ait x [ i ] x[i] x[i] Article (s),Nous pouvons suivre 2 Diviser par la puissance , Diviser en : 1 , 2 , 4 , . . . , 2 k − 1 , x [ i ] − 2 k + 1 1, 2, 4, ..., 2^{k-1}, x[i] - 2^{k} + 1 1,2,4,...,2k1,x[i]2k+1
  Parmi eux k k k Est la plus grande satisfaction x [ i ] − 2 k + 1 ≥ 0 x[i] - 2^{k} + 1 \ge 0 x[i]2k+10 Entier non négatif de.
  Voilà.,1 À x [ i ] x[i] x[i] Tous les entiers entre k + 1 k+1 k+1 Les chiffres se combinent. , Donc, il suffit de le démonter. k + 1 k+1 k+1 Article (s), Toutes prises k ( 0 ≤ k ≤ x [ i ] ) k (0 \le k \le x[i]) k(0kx[i]) Chaque élément peut être pris en considération .
  Exemples,Quand x [ i ] = 14 x[i] = 14 x[i]=14 Heure, Peut être divisé en 1,2,4,7 Article (s), Alors, quand on va prendre 13 Quand il s'agit de ce genre de choses, , Équivalent au choix 2、4、7,Les capacités sont respectivement de c [ i ] ∗ 2 , c [ i ] ∗ 4 , c [ i ] ∗ 7 c[i]*2, c[i]*4, c[i]* 7 c[i]2,c[i]4,c[i]7, Les valeurs sont w [ i ] ∗ 2 , w [ i ] ∗ 4 , w [ i ] ∗ 7 w[i]*2, w[i]*4, w[i]* 7 w[i]2,w[i]4,w[i]7.
   Par cette méthode de fractionnement , x [ i ] x[i] x[i] Jusqu'à l o g 2 x [ i ] log_2 {x[i]} log2x[i] Article (s),Et ensuite 0/1 Solution de sac à dos , Nous obtenons une complexité temporelle de O ( m ∑ i = 1 n l o g 2 x [ i ] ) O(m\sum_{i=1}^{n}log_2{x[i]}) O(mi=1nlog2x[i]) Algorithme.
   En savoir plus sur les sacs à dos multiples ,Peut être référencé:.Algorithme d'écriture silencieuse tard dans la nuit(16.)- Sac à dos multiple .

4、 Sac à dos de groupe

  Oui. n ( n ≤ 1000 ) n(n \le 1000) n(n1000) Articles et une capacité de m ( m ≤ 1000 ) m(m \le 1000) m(m1000) Sac à dos. Ces articles sont divisés en groupes ,No i i i Articles appartenant à g [ i ] g[i] g[i] Groupe,La capacité est c [ i ] c[i] c[i], La valeur est w [ i ] w[i] w[i], Vous devez maintenant choisir des articles à mettre dans votre sac à dos , Et un maximum d'un article par groupe , La capacité totale ne doit pas dépasser la capacité du sac à dos , Trouver la valeur totale maximale de l'article qui peut être atteint .

   Voici une description complète du problème du sac à dos de groupe , La différence avec les autres problèmes de sac à dos est que chaque article a un numéro de groupe supplémentaire , Et dans le même groupe , Vous ne pouvez sélectionner qu'un seul article dans votre sac à dos ; Parce qu'il n'y a qu'un seul objet , Pour que les lecteurs puissent oublier Sac à dos complet Et Sac à dos multiple Le concept de, Avant de regarder en bas , Rappelle - toi d'abord. 0/1 Équation de transfert d'état du sac à dos .

  Première étape:Prétraitement;
   Commencez par chaque article par le numéro de groupe g [ i ] g[i] g[i] Trier de petit à grand, Supposons qu'il y ait au total t t t Groupe,Alors g [ i ] g[i] g[i] Discrète dans l'ordre [ 1 , t ] [1,t] [1,t] Entier positif de. L'objectif est de g [ i ] g[i] g[i] Mapper dans le tableau d'état comme indice ;

  Deuxième étape: État de la conception ;
  Statut ( k , j ) (k, j) (k,j) Indique avant k k k Les articles du Groupe sont placés exactement dans la capacité j j j Sac à dos ( k ∈ [ 0 , t ] , j ∈ [ 0 , m ] ) (k \in [0, t], j \in [0, m]) (k[0,t],j[0,m]);Ordre d p [ k ] [ j ] dp[k][j] dp[k][j] État de la représentation ( k , j ) (k, j) (k,j) Valeur maximale du sac à dos , Avant k k k Articles de groupe ( Sélectionner un ou plusieurs articles par groupe ) Juste dans la capacité de j j j Valeur totale maximale du sac à dos ;

  Troisième étape: Liste des équations de transfert d'état : d p [ k ] [ j ] = m a x ( d p [ k − 1 ] [ j ] , d p [ k − 1 ] [ j − c [ i ] ] + w [ i ] ) dp[k][j] = max(dp[k-1][j], dp[k-1][j - c[i]] + w[i]) dp[k][j]=max(dp[k1][j],dp[k1][jc[i]]+w[i]) k = g [ i ] k = g[i] k=g[i] Parce qu'il n'y a que deux cas par article :
  1)Non.:Si “No i i i Article (s)(Appartient à la k k k Groupe) Ne pas placer la capacité comme j j j Sac à dos”, Alors le problème se traduit par “Avant k − 1 k-1 k1 Les articles du Groupe sont placés dans une capacité de j j j Sac à dos” La question de; Parce qu'il n'y a pas de place , Donc la valeur maximale est égale à “Avant k − 1 k-1 k1 Les articles du Groupe sont placés dans une capacité de j j j Sac à dos” Valeur maximale , Dans l'équation de transfert d'état correspondante d p [ k − 1 ] [ j ] dp[k-1][j] dp[k1][j];
  2)Pose ça.:Si “No i i i Article (s)(Appartient à la k k k Groupe) Capacité de mise en place j j j Sac à dos”, Alors le problème se traduit par “Avant k − 1 k-1 k1 Les articles du Groupe sont placés dans une capacité de j − c [ i ] j-c[i] jc[i] Sac à dos” La question de; Alors la valeur maximale est égale à “Avant k − 1 k-1 k1 Les articles du Groupe sont placés dans une capacité de j − c [ i ] j-c[i] jc[i] Sac à dos” Valeur maximale Ajouter le paragraphe suivant: i i i Valeur des articles ,C'est - à - dire: d p [ k − 1 ] [ j − c [ i ] ] + w [ i ] dp[k-1][j - c[i]] + w[i] dp[k1][jc[i]]+w[i];
  Parce que Avant k − 1 k-1 k1 Il ne doit pas y avoir de k k k Articles du Groupe , Pour pouvoir satisfaire “ Un maximum. ” Cette condition;

  Pour n n n Mettre les articles dans une capacité de m m m Sac à dos, Le nombre d'états est O ( n m ) O(nm) O(nm), La consommation par transfert d'état est O ( 1 ) O(1) O(1), Donc la complexité temporelle de l'ensemble du processus de transition d'état est O ( n m ) O(nm) O(nm);
   Notez que lorsque le paquet est résolu , Pour s'assurer que les mêmes groupes sont réunis , Et le prétraitement initial et la discrétisation sont formels pour s'assurer que ,Voilà., Le numéro de groupe de chaque article est g [ i ] = 1 , 2 , 3 , 4... , t g[i] = 1,2,3,4...,t g[i]=1,2,3,4...,t, Et nous pouvons également exprimer l'équation de transfert d'état en somme k k k Non pertinent,Comme suit: d p [ g [ i ] ] [ j ] = m a x ( d p [ g [ i ] − 1 ] [ j ] , d p [ g [ i ] − 1 ] [ j − c [ i ] ] + w [ i ] ) dp[ g[i] ][j] = max(dp[ g[i]-1][j], dp[ g[i]-1][j - c[i]] + w[i]) dp[g[i]][j]=max(dp[g[i]1][j],dp[g[i]1][jc[i]]+w[i])
   Plus de détails sur les sacs à dos groupés ,Peut être référencé:.Algorithme d'écriture silencieuse tard dans la nuit(XVII.)- Sac à dos de groupe .

5、 Dépend du sac à dos

   Dans les magasins n ( n ≤ 50 ) n(n \le 50) n(n50) Une boîte., Prix par boîte p [ i ] ( p [ i ] ≤ 1000 ) p[i](p[i] \le 1000) p[i](p[i]1000),Valeur: 0, Il y a des petits cadeaux dans la boîte. ,La quantité est m [ i ] ( 1 ≤ m [ i ] ≤ 10 ) m[i](1 \le m[i] \le 10) m[i](1m[i]10), Chaque petit cadeau est décrit comme un double ( c , v ) (c, v) (c,v), c c c Pour le prix , v v v Pour la valeur , Si vous achetez un petit cadeau , Il faut d'abord acheter la boîte. . Maintenant, donnez le prix. m ( m ≤ 100000 ) m(m \le 100000) m(m100000), Trouver la valeur maximale disponible .

   C'est un problème particulier de sac à dos dépendant , C'est aussi le cas le plus simple dans un sac à dos. , Où la boîte est Partie principale , Petit cadeau comme Annexe. Vous souhaitez acheter des accessoires , Vous devez d'abord acheter la partie principale ,C'est ce qu'on appelle “Dépendance” ;

  Première étape: État de la conception ;
  Statut ( i , j ) (i, j) (i,j) Indique avant i i i Le prix d'une boîte est exactement j j j ( i ∈ [ 0 , n ] , j ∈ [ 0 , m ] ) (i \in [0, n], j \in [0, m]) (i[0,n],j[0,m]);
  Ordre d p [ i ] [ j ] dp[i][j] dp[i][j] État de la représentation ( i , j ) (i, j) (i,j) Valeur maximale obtenue sous , Avant i i i Le prix d'achat de chaque boîte est de j j j Valeur totale maximale obtenue dans le cas de ;

   Nous sommes en état de conception , N'a pas conçu de petits cadeaux à l'état , Comment faire un changement d'état? ?
Insérer la description de l'image ici
   On peut y penser. , Laisse tomber les petits cadeaux. , Chaque boîte n'a que deux états. ,Choisir Et Non.;
  1)Choisir: C'est un petit cadeau dans cette boîte. 0/1 Sac à dos;
  2)Non.: Ça n'a rien à voir avec les petits cadeaux dans cette boîte. , Directement égal à avant i − 1 i-1 i1 Valeur maximale des boîtes ,C'est - à - dire: d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j].
  Alors, Il suffit d'énumérer toutes les boîtes de l'avant vers l'arrière , p [ i ] p[i] p[i] Pour i i i Prix par boîte , w [ i ] w[i] w[i] Pour la valeur , La boîte n'a pas de valeur à cause de ce problème. ,C'est - à - dire: w [ i ] w[i] w[i] Équivalent à zéro ;

Effectuer les trois étapes suivantes: :
  1)Tout d'abord,, Buy No. i i i Une boîte., Et ne pas mettre d'articles ;
  2)Et puis, Maintenant que les boîtes ont été achetées , Pour être rassuré i i i Un petit cadeau dans une boîte. 0/1 Le sac à dos. ;
  3)Enfin,C'est exact. Acheter une boîte i i i Et Pas de boîte. i i i Prendre la valeur maximale une fois ;

   Buy No. i i i Une boîte., Ça doit être le passé. i − 1 i-1 i1 L'état des boîtes est calculé. , L'équation de transfert d'état est donnée comme suit: :
d p [ i ] [ j ] = { i n f j < p [ i ] ( 1 ) d p [ i − 1 ] [ j − p [ i ] ] + w [ i ] j ≥ p [ i ] ( 2 ) dp[i][j] =\begin{cases}inf & j < p[i] & (1)\\dp[i-1][j - p[i]]+w[i] & j \ge p[i] & (2)\end{cases} dp[i][j]={ infdp[i1][jp[i]]+w[i]j<p[i]jp[i](1)(2)

  • (1) Ça veut dire qu'il n'y a pas assez d'argent. , Une désolation infinie ;(2) Représentant de Avant i − 1 i-1 i1 Prix par boîte j − p [ i ] j - p[i] jp[i] Heure,Encore. p [ i ] p[i] p[i] Achetez le numéro. i i i Cas de boîtes .À ce moment - là. d p [ i ] [ j ] dp[i][j] dp[i][j] Représentant: No i i i Après avoir acheté une boîte , Avant d'acheter un petit cadeau ,Capacité: j j j Valeur totale maximale ;

   Maintenant que les boîtes ont été achetées , Pour être rassuré i i i Un petit cadeau dans une boîte d p [ i ] [ 0... m ] dp[i][0...m] dp[i][0...m] Aller de l'avant 0/1 Le sac à dos. ; Après avoir énuméré tous les petits cadeaux, ,Je l'ai. d p [ i ] [ j ] dp[i][j] dp[i][j] Représentant: No i i i Une boîte. , Et après avoir acheté quelques petits cadeaux, ,Capacité: j j j Valeur totale maximale ;

  Enfin, Oui. Cette boîte Et N'achète pas cette boîte. Faire un choix , C'est - à - dire prendre la valeur maximale une fois ,Comme suit: d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i − 1 ] [ j ] ) dp[i][j] = max(dp[i][j], dp[i-1][j]) dp[i][j]=max(dp[i][j],dp[i1][j])
  Ici. d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j] Ce qui représente exactement i i i Cas où une boîte n'est pas achetée .
   En savoir plus sur la dépendance au sac à dos ,Peut être référencé:.Algorithme d'écriture silencieuse tard dans la nuit(Dix - huit.)- Dépend du sac à dos .

Six、ArbreDP

  Un arbre donné n ( n < = 150 ) n(n <= 150) n(n<=150) Arbre à noeuds , Enlevez quelques bords. , De sorte qu'un P P P Blocs connectés de noeuds . Demandez combien de bords au moins peuvent être enlevés pour répondre à cette exigence. .

  Comme le montre la figure,Un arbre. 10 Arbre à noeuds , On peut enlever les bords rouges. , En deux sous - arbres. ,Respectivement: 3 Noeuds et 7Noeuds.
Insérer la description de l'image ici
   Ou de cette façon , Trois sous - arbres. ,Respectivement: 5 、4、1 Noeuds.
Insérer la description de l'image ici
   Pour un noeud dans l'arbre ( Noeud rouge comme indiqué ), Vous pouvez choisir de supprimer les bords du sous - arbre de connexion , Vous pouvez aussi choisir de garder ; Chaque bord qui relie un sous - arbre Choisir Et Non., Peut obtenir une combinaison , Correspond au problème du sac à dos , Et un seul choix par sous - arbre , Correspond à un sac à dos groupé , Donc vous pouvez utiliser cette idée pour concevoir l'état .
Insérer la description de l'image ici
   Conception de l'état :Avec d p [ u ] [ x ] dp[u][x] dp[u][x] Exprimé par u u u Sous - arbre à racine , En enlevant quelques bords, on obtient exactement x x x Bloc de connexion du noeud ( Notez que seule la partie de l'arbre qui contient son enfant , Ne pas connecter son noeud parent ) Consommation minimale ;
   Idées de transfert d'état :Enumeration u u u Tous les sous - noeuds de , Pour les sous - noeuds v v v, Calcul récursif d p [ v ] [ i ] ( 1 < = i < = x ) dp[v][i] (1 <= i <= x) dp[v][i](1<=i<=x) Toutes les situations possibles ,Si d p [ v ] [ i ] dp[v][i] dp[v][i] Existe, Est considéré comme une capacité de i i i,Valeur: d p [ v ] [ i ] dp[v][i] dp[v][i] Articles,Exprimé en ( i , d p [ v ] [ i ] ) (i, dp[v][i]) (i,dp[v][i]). Et au noeud u u u Un sac à dos de groupe .
  Situation initiale: Pour n'importe quel noeud u u u, Son nombre de noeuds enfants est c u c_u cu, La situation initiale est d p [ u ] [ 1 ] = c u dp[u][1] = c_u dp[u][1]=cu, Indique si le noeud actuel est un point isolé , Alors aucun de ses sous - arbres ne peut être sélectionné , Donc le coût est d'enlever tous les bords du sous - arbre connecté , Nombre de sous - arbres .
  Changement d'état: Et pour chaque sous - arbre, v v v De k k k Blocs connectés de noeuds ,La réponse est d p [ v ] [ j − k ] + d p [ v ] [ k ] − 1 dp[v][j-k] + dp[v][k] - 1 dp[v][jk]+dp[v][k]1,Attention ici -1 Signification de, Parce qu'au début, par défaut, nous enlevons tous les bords des sous - arbres connectés , C'est pour ça qu'il faut le refaire. .
   Traitement des réponses : La dernière réponse est min ⁡ ( d p [ x ] [ P ] + ( 1   i f   x   i s   n o t   r o o t ) \min(dp[x][P] + (1 \ if \ x \ is \ not \ root) min(dp[x][P]+(1 if x is not root); Considérer le noeud comme P Les blocs connectés de :1) Bloc relié au noeud racine ,Alors la réponse est d p [ r o o t ] [ P ] dp[root][P] dp[root][P];2) Bloc non relié au noeud racine , Tous les noeuds doivent être énumérés d p [ x ] [ P ] + 1 dp[x][P] +1 dp[x][P]+1 Prenez le minimum, Y en a ici. 1 Pour couper ( p a r e n t [ x ] , x ) (parent[x], x) (parent[x],x) Consommation de ce côté ;

Sept、 Matrice dichotomique

A n = [ a 11 a 12 ⋯ a 1 m a 21 a 22 ⋯ a 2 m ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m m ] n A^n=\begin{bmatrix} {a_{11}}&{a_{12}}&{\cdots}&{a_{1m}}\\ {a_{21}}&{a_{22}}&{\cdots}&{a_{2m}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{m1}}&{a_{m2}}&{\cdots}&{a_{mm}}\\ \end{bmatrix}^n An=a11a21am1a12a22am2a1ma2mammn
   Pour les matrices n n n Puissance secondaire, Si une simple multiplication continue est utilisée pour résoudre , Cette complexité temporelle est totalement inacceptable , Nous pensons à la puissance binaire rapide des entiers mentionnés précédemment (.Algorithme d'écriture silencieuse tard dans la nuit(30.)- Puissance rapide binaire ), Il en va de même pour les matrices ;
A n = { I n = 0 ( A n − 1 2 ) 2 × A n Pour C'est bizarre. Nombre ( A n 2 ) 2 n Pour Non Zéro. Oui. Nombre A^{n} = \begin{cases} I & n = 0\\ (A^{\frac{n-1}{2}})^2 \times A& n C'est un nombre impair\\ (A^{\frac{n}{2}})^2 & n Est un nombre pair non nul \end{cases} An=I(A2n1)2×A(A2n)2n=0nPourC'est bizarre.NombrenPourNonZéro.Oui.Nombre
   Plus de moules. 、 Propriétés de la multiplication modulaire , La matrice satisfait également à l'opération de puissance modulaire ,C'est - à - dire::
A n m o d    M = { I m o d    M n = 0 ( A n − 1 2 ) 2 × A m o d    M n Pour C'est bizarre. Nombre ( A n 2 ) 2 m o d    M n Pour Non Zéro. Oui. Nombre A^{n} \mod M = \begin{cases} I \mod M & n = 0\\ (A^{\frac{n-1}{2}})^2 \times A \mod M & n C'est un nombre impair\\ (A^{\frac{n}{2}})^2 \mod M & n Est un nombre pair non nul \end{cases} AnmodM=ImodM(A2n1)2×AmodM(A2n)2modMn=0nPourC'est bizarre.NombrenPourNonZéro.Oui.Nombre
  Et ainsi de suite.,Pour m m m Matrice d'ordre A A A, La complexité temporelle peut être réduite à O ( m 3 l o g n ) O(m^3log_n) O(m3logn);
   Ou la question au début de cet article , Comment calculer Fibonacci n n n Modèle de terme M M M ? Croyez que les lecteurs intelligents y ont pensé. , Notre personnage principal est :Matrice
   Commençons par la formule récursive. :
f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n) = f(n-1) + f(n-2) f(n)=f(n1)+f(n2)   Et nous avons pensé :1 - Oui. 2 × 2 2 \times 2 2×2 Matrice et 1 - Oui. 2 × 1 2 \times 1 2×1 Multiplication matricielle de , J'en ai toujours un. 2 × 1 2 \times 1 2×1 La matrice de;
  Tout d'abord,, Remplir avec une formule récursive Vecteur de colonne Et Matrice :
[ f ( n ) ? ] = [ 1 1 ? ? ] [ f ( n − 1 ) f ( n − 2 ) ] \left[ \begin{matrix} f(n) \\ ? \end{matrix} \right] = \left[ \begin{matrix} 1 & 1 \\ ? & ?\end{matrix} \right] \left[ \begin{matrix} f(n-1) \\ f(n-2)\end{matrix} \right] [f(n)?]=[1?1?][f(n1)f(n2)]   Ensuite, le vecteur de colonne avec le point d'interrogation est complété par la transitivité du vecteur de colonne ,Je l'ai.:
[ f ( n ) f ( n − 1 ) ] = [ 1 1 ? ? ] [ f ( n − 1 ) f ( n − 2 ) ] \left[ \begin{matrix} f(n) \\ f(n-1)\end{matrix} \right] = \left[ \begin{matrix} 1 & 1 \\ ? & ?\end{matrix} \right] \left[ \begin{matrix} f(n-1) \\ f(n-2)\end{matrix} \right] [f(n)f(n1)]=[1?1?][f(n1)f(n2)]   Compléter la matrice des coefficients avec des points d'interrogation ,Je l'ai.:
[ f ( n ) f ( n − 1 ) ] = [ 1 1 1 0 ] [ f ( n − 1 ) f ( n − 2 ) ] \left[ \begin{matrix} f(n) \\ f(n-1)\end{matrix} \right] = \left[ \begin{matrix} 1 & 1 \\ 1 & 0\end{matrix} \right] \left[ \begin{matrix} f(n-1) \\ f(n-2)\end{matrix} \right] [f(n)f(n1)]=[1110][f(n1)f(n2)]   Et puis nous avons fait une réduction progressive ,Je l'ai.:
[ f ( n ) f ( n − 1 ) ] = [ 1 1 1 0 ] [ f ( n − 1 ) f ( n − 2 ) ] = [ 1 1 1 0 ] [ 1 1 1 0 ] [ f ( n − 2 ) f ( n − 3 ) ] = [ 1 1 1 0 ] ⋯ [ 1 1 1 0 ] ⏟ n − 1 [ f ( 1 ) f ( 0 ) ] \begin{aligned} \left[ \begin{matrix} f(n) \\ f(n-1)\end{matrix} \right] &= \left[ \begin{matrix} 1 & 1 \\ 1 & 0\end{matrix} \right] \left[ \begin{matrix} f(n-1) \\ f(n-2)\end{matrix} \right] \\ &= \left[ \begin{matrix} 1 & 1 \\ 1 & 0\end{matrix} \right] \left[ \begin{matrix} 1 & 1 \\ 1 & 0\end{matrix} \right] \left[ \begin{matrix} f(n-2) \\ f(n-3)\end{matrix} \right] \\ &=\underbrace{ \left[ \begin{matrix} 1 & 1 \\ 1 & 0\end{matrix} \right] {\cdots}\left[ \begin{matrix} 1 & 1 \\ 1 & 0\end{matrix} \right] }_{n-1} \left[ \begin{matrix} f(1) \\ f(0)\end{matrix} \right] \\ \end{aligned} [f(n)f(n1)]=[1110][f(n1)f(n2)]=[1110][1110][f(n2)f(n3)]=n1 [1110][1110][f(1)f(0)]  Enfin, Selon la loi de combinaison de multiplication de matrice , Fusionner les matrices précédentes ,Je l'ai.:
[ f ( n ) f ( n − 1 ) ] = [ 1 1 1 0 ] n − 1 [ f ( 1 ) f ( 0 ) ] = A n − 1 [ 1 0 ] \begin{aligned} \left[ \begin{matrix} f(n) \\ f(n-1)\end{matrix} \right] &=\left[ \begin{matrix} 1 & 1 \\ 1 & 0\end{matrix} \right]^{n-1}\left[ \begin{matrix} f(1) \\ f(0)\end{matrix} \right] \\ &=A^{n-1}\left[ \begin{matrix} 1 \\ 0 \end{matrix} \right] \end{aligned} [f(n)f(n1)]=[1110]n1[f(1)f(0)]=An1[10]  Et donc,, Il suffit d'utiliser la puissance binaire de la matrice A n − 1 m o d    M A^{n-1} \mod M An1modM , Multiplier par le vecteur de colonne initial [ 1 0 ] \left[ \begin{matrix} 1 \\ 0 \end{matrix} \right] [10], Le premier élément du vecteur de colonne obtenu est la solution du problème. ;
  En fait, Il suffit de lister les équations de transition d'état ,Quand n n n Quand c'est grand, Nous pouvons utiliser la puissance binaire rapide de la matrice pour résoudre la récurrence .
   Plus de détails sur la dichotomie matricielle ,Peut être référencé:.Algorithme d'écriture silencieuse tard dans la nuit(Vingt.)- Puissance rapide de la matrice.

Huit、SectionDP

  Oui. n ( n ≤ 100 ) n(n \le 100) n(n100) Des tas de pierres en rangées. ,No i i i Le poids de la pile est w i w_i wi, Maintenant, nous allons fusionner les pierres dans un tas séquentiel . Spécifiez que vous ne pouvez sélectionner que deux piles adjacentes à la fois et les combiner en une nouvelle pile , La consommation combinée est le poids total des pierres actuellement combinées. . Concevoir un algorithme , Calculer n n n Consommation minimale de pierres en tas .

   En pensant à la programmation dynamique, , Nous pouvons commencer par penser que si nous développons tous les scénarios , Que se passe - t - il? .
   Pour cette question, , La première décision que nous avons prise était de choisir une paire de pierres adjacentes à fusionner ,En tout. n − 1 n-1 n1 Situation;Pour 5Pile L'état des pierres ,No 1 Total des fusions 4 Sélection des espèces:

  • 1)Sélectionner No 1 Pile Et No 2 Pile Les pierres sont fusionnées ,Comme le montre la figure:
  • 2)Sélectionner No 2 Pile Et No 3 Pile Les pierres sont fusionnées ,Comme le montre la figure:
  • 3)Sélectionner No 3 Pile Et No 4 Pile Les pierres sont fusionnées ,Comme le montre la figure:
  • 4)Sélectionner No 4 Pile Et No 5 Pile Les pierres sont fusionnées ,Comme le montre la figure:
    Insérer la description de l'image ici
       L'une ou l'autre de ces situations transforme les pierres en 4 Pile, Et c'est devenu une solution 4 4 4 Problèmes de remblai rocheux ; On peut faire de même. , Transformer les pierres en 3 3 3 Pile, 2 2 2 Pile, Et finalement 1 1 1 Pile, Pour trouver la solution finale au problème .
      Bien sûr.,C'est un processus récursif, Le nombre de tas de pierres peut être réduit d'un par fusion , Total n − 1 n-1 n1 Fusion secondaire, Le nombre de solutions possibles à chaque étape est une relation multiplicative , Le nombre total de programmes ( n − 1 ) ! (n-1)! (n1)!;
      Par exemple, Le reste de ce qui est mentionné ci - dessus. 4 Stockpile , L'arbre de recherche qui énumère toutes les solutions possibles à l'aide d'une recherche en profondeur est illustré dans la figure. :
    Insérer la description de l'image ici
      Utilisé dans la figure ‘-’ Représente un séparateur entre différents tas de pierres ,C'est - à - dire: 1-2-3-4 Représentant 4 État du tas ,12-3-4Représentation No 1 Pile Et par. 2 Pile Situation consolidée . Pour une telle variété de solutions, la consommation totale est la plus faible , L'exactitude est garantie , Parce que nous avons énuméré toutes les situations , Mais le temps est certainement inacceptable. .
      Alors, Comment optimiser la recherche ? La difficulté que nous avons à trouver ce problème est : Après la fusion des deux pierres sélectionnées, , Son poids devient la somme combinée ,Pour n n n Stockpile ,Sélectionné n − 1 n-1 n1 Mode de fusion , Ils arrivent dans des états différents. , Impossible de stocker l'état .
       Quand il n'y a aucune idée , Nous essayons de penser à l'envers. ; Nous avons constaté que tous les noeuds foliaires de cet arbre de recherche prioritaire en profondeur sont les mêmes , C'est une percée dans la résolution de nos problèmes. ;Pour [ 1 , n ] [1, n] [1,n] Stockpile , Supposons que vous ayez fusionné n − 2 n-2 n2 Une fois, Il ne reste plus que ça. Deux tas de pierres , Donc nous devons juste fusionner pour la dernière fois , Pour transformer deux tas de pierres en un seul. , Supposons que la dernière fusion ait eu lieu à k k k, C'est - à - dire qu'il reste deux piles : [ 1 , k ] [1, k] [1,k] Et [ k + 1 , n ] [k+1, n] [k+1,n], Comme le montre la figure 2. -2-1Comme indiqué:Insérer la description de l'image ici  Attention!,À ce moment - là. [ 1 , k ] [1, k] [1,k] Et [ k + 1 , n ] [k+1, n] [k+1,n] Ils ont fusionné en un tas. , Donc nous avons transformé la question en une demande [ 1 , k ] [1, k] [1,k] Consommation minimale combinée d'un tas ,Et [ k + 1 , n ] [k+1, n] [k+1,n] Consommation minimale combinée en tas ; Et ici k k k La plage de valeurs pour [ 1 , n − 1 ] [1, n-1] [1,n1];
       En utilisant cette méthode , Réduire progressivement l'intervalle à 1, Et vous obtenez la solution à l'ensemble du problème .Ordre f [ i ] [ j ] f[i][j] f[i][j] De No i i i Pile Stone to No j j j Pile Coût minimal de la fusion des pierres en un tas .   f [ i ] [ j ] = { 0 i = j min ⁡ k = i j − 1 ( f [ i ] [ k ] + f [ k + 1 ] [ j ] + c o s t ( i , j ) ) i ≠ j f[i][j] = \begin{cases} 0 & i=j\\ \min_{k=i}^{j-1}(f[i][k] + f[k+1][j] + cost(i,j)) & i \neq j\end{cases} f[i][j]={ 0mink=ij1(f[i][k]+f[k+1][j]+cost(i,j))i=ji=j
      Parmi eux c o s t ( i , j ) = ∑ k = i j w k cost(i, j) = \sum_{k=i}^{j}w_k cost(i,j)=k=ijwk
      Avec ça “ Positif et négatif ” Explication, Cette équation de transfert d'état est bien comprise ;
        1)Quand i = j i=j i=j Heure,Parce que f [ i ] [ j ] f[i][j] f[i][j] C'est déjà un tas. , Donc la consommation est naturellement 0 C'est;
        2)Quand i ≠ j i \neq j i=j Heure, Nous devons combiner les deux piles restantes en une pile , Une pile. f [ i ] [ k ] f[i][k] f[i][k] , L'autre pile est f [ k + 1 ] [ j ] f[k+1][j] f[k+1][j], La consommation combinée de ces deux piles est De No i i i Pile à la j j j Somme du poids de la pile ,C'est - à - dire: c o s t ( i , j ) = ∑ k = i j w k cost(i, j) = \sum_{k=i}^{j}w_k cost(i,j)=k=ijwk, Et pour le système de fusion ,Total k = j − i k=j-i k=ji Sélection des espèces, Donc l'énumération j − i j-i ji Une fois, Le plus petit est la réponse. .
       Résolution par recherche de mémoire f [ 1 ] [ n ] f[1][n] f[1][n] C'est la dernière réponse. .
       Diagramme dynamique comme indiqué , Montre l'ordre des solutions itératives , La grille grise représente un état invalide , La grille rouge représente la longueur 2 Intervalle de, La grille orange représente la longueur 3 Intervalle de, La grille dorée représente la longueur 4 Intervalle de, La grille jaune représente l'état final de l'intervalle que nous exigeons ,C'est - à - dire: f [ 1 ] [ 5 ] f[1][5] f[1][5].
    Insérer la description de l'image ici
       Intervalle pertinent DP Plus en profondeur ,Peut être référencé:.Algorithme d'écriture silencieuse tard dans la nuit(27.)- SectionDP.

Neuf、NumériqueDP

   Si tous les chiffres d'un nombre sont additionnés 10 10 10 Multiple de, Est appelé g o o d   n u m b e r good \ number good number, Intervalle de recherche [ l , r ] ( 0 ≤ l ≤ r ≤ 1 0 18 ) [l, r](0 \le l \le r \le 10^{18}) [l,r](0lr1018) Intérieur g o o d   n u m b e r good \ number good number Nombre de;

  Sur cette question, L'algorithme simple est d'énumérer chaque nombre dans l'intervalle , Et juger de la faisabilité ,La complexité temporelle est o ( ( r − l ) c ) o((r-l)c) o((rl)c), c = 19 c=19 c=19, Ça doit être inacceptable. .
  Pour les intervalles [ l , r ] [l, r] [l,r] Nombre de quantités satisfaites en interne , Les problèmes peuvent être décomposés par la méthode des différences ;
  Hypothèses [ 0 , x ] [0, x] [0,x] Intérieur g o o d   n u m b e r good \ number good number La quantité est g x g_x gx,Donc la Section [ l , r ] [l, r] [l,r] La quantité à l'intérieur est g r − g l − 1 g_r - g_{l-1} grgl1; Les mêmes méthodes sont utilisées pour calculer g r g_r gr Et g l − 1 g_{l-1} gl1, Puis soustrayez - le. ;
Insérer la description de l'image ici
   Si un nombre i i i Satisfaction i < x i < x i<x,Alors i i i Il doit y avoir quelqu'un de haut en bas. , De sorte que la valeur à ce chiffre soit inférieure à x x x Valeur numérique sur le bit correspondant , Et tous les sommets précédents x x x Bits égaux sur .
  Par exemple,,Quand x = 1314 x = 1314 x=1314 Heure, i = 0 a b c i=0abc i=0abc i = 12 a b i=12ab i=12ab i = 130 a i=130a i=130a i = 1312 i=1312 i=1312,Alors pour i i i En termes, Quel que soit le nombre de lettres qui suivent , C'est de la satisfaction. i < x i < x i<x À cette condition. .
Insérer la description de l'image ici
   Si nous demandons g 1314 g_{1314} g1314 Valeur de, Vous pouvez énumérer les bits supérieurs : Lorsque le BIT le plus élevé est 0, Alors le problème se transforme en g 999 g_{999} g999 Sous - Questions ; Lorsque le BIT le plus élevé est 1, Le problème se transforme en g 314 g_{314} g314 Sous - Questions .
   g 314 g_{314} g314 Peut continuer à résoudre Récursivement ,Et g 999 g_{999} g999 Parce que chaque plage de chiffres est [ 0 , 9 ] [0,9] [0,9], Peut être transformé en un problème général de programmation dynamique pour résoudre .

   L'état du préfixe ici correspond à ce qui a été mentionné précédemment. Certaines conditions ;
  Dans cette question,, L'état du préfixe est décrit comme suit: : La somme des chiffres d'un préfixe numérique 10Prends le reste(Module)Valeur de. Le processus de changement de l'état du préfixe est illustré dans la figure :

   Dans la question précédente , La signification de l'état du préfixe est : Pour un nombre 520 , On n'a pas besoin de dossiers. 520 , Et il suffit d'enregistrer 7;Pour 52013, On n'a pas besoin de dossiers. 52013, Et il suffit d'enregistrer 1. C'est comme ça que l'état de masse initial , Est devenu le plus 10 Statut.
   Sur la base des trois informations ci - dessus , Nous pouvons énumérer les chiffres de haut en bas i i i Chacun d'eux , Transformer les problèmes en petits problèmes étape par étape .
  Nous pouvons définir f ( n , s t , l i m ) f(n, st, lim) f(n,st,lim) Indique que le reste doit être considéré n n n Les chiffres, L'état du préfixe pour la composition de haut niveau déjà énumérée est s t st st,Et utiliser l i m lim lim Indique le numéro actuel n n n BIT peut - il obtenir la valeur maximale (Pour b b b Décimal, La valeur maximale est b − 1 b-1 b1,Par exemple, 10 Dans l'état décimal , La valeur maximale est 9) Nombre de chiffres . Expliquons ce que signifie cette représentation tridimensionnelle. :

  • 1) Le BIT de l'énumération actuelle est n n n Bits, n n n Haut Représentant , Faible représentation ;
  • 2) s t st st Est l'état du préfixe ,Dans cette question,, Représente tous les bits supérieurs qui ont été énumérés ( Préfixe numérique ) La somme des chiffres 10Prends le reste(Module).Attention!: Nous ne nous soucions pas de chaque chiffre du préfixe , Tout ce qui compte, c'est qu'ils ajoutent des matrices. 10 Quelle est la valeur après .
  • 3) l i m = t r u e lim=true lim=true Indique que l'un des bits supérieurs énumérés est déjà plus élevé que l'autre x x x Petit nombre de bits correspondants , La valeur maximale de chaque nombre énuméré ci - dessous n'est plus x x x Contrôle;Sinon, La valeur maximale devrait être x x x Bits correspondants de .Exemples, Quand le nombre décimal x = 1314 x = 1314 x=1314 Heure, Les trois premiers chiffres de l'énumération vers le haut sont: “131”, l i m = f a l s e lim = false lim=false, Donc la valeur d'intervalle du quatrième chiffre est [ 0 , 4 ] [0,4] [0,4]; Les trois premiers chiffres de l'énumération sont: “130” Heure, l i m = t r u e lim = true lim=true, Donc la valeur d'intervalle du quatrième chiffre est [ 0 , 9 ] [0, 9] [0,9].
      Alors..., Nous sommes en accord avec l'état ci - dessus ,Prétraitement x x x Chaque chiffre de , Exprimé en décimales comme suit: : x = d n d n − 1 . . . d 1 x = d_nd_{n-1}...d_1 x=dndn1...d1 (Parmi eux d n d_n dn Représentant la position la plus élevée , d 1 d_1 d1 Représentant le plus bas )
       L'équation de transfert d'état est la suivante: : f ( n , s t , l i m ) = ∑ k = 0 m a x v f ( n − 1 , ( s t + k ) m o d    10 , l i m   o r   ( k < m a x v ) ) \begin{aligned}& f(n, st, lim) \\ &= \sum_{k=0}^{maxv} f(n-1, (st+k) \mod 10, lim \ or \ (k < maxv))\end{aligned} f(n,st,lim)=k=0maxvf(n1,(st+k)mod10,lim or (k<maxv))
       k k k Indique le paragraphe n n n Quel est le nombre de bits? ,Son champ d'application est [ 0 , m a x v ] [0, maxv] [0,maxv];
       m a x v maxv maxv Indique le paragraphe n n n Valeur maximale que le BIT peut obtenir ,Elle a été créée par l i m lim lim Décide que,C'est - à - dire::
       m a x v = { 9 l i m = t r u e d n l i m = f a l s e maxv = \begin{cases}9 & lim = true\\d_n & lim = false\end{cases} maxv={ 9dnlim=truelim=false
       En utilisant l'équation de transfert d'état ci - dessus , Nous pouvons résoudre Récursivement ,Et quand n = 0 n=0 n=0 C'est une sortie récursive. , Étant donné que les chiffres doivent satisfaire à la somme de tous les chiffres, 10 10 10 Multiple de,Alors seulement s t = 0 st = 0 st=0 La situation est légale. ,En d'autres termes,,Quand n = 0 n=0 n=0 Heure,Oui.: f ( 0 , x , l i m ) = { 1 x = 0 0 0 < x ≤ 9 f(0, x, lim) = \begin{cases} 1 & x = 0\\ 0 & 0 \lt x \le 9\end{cases} f(0,x,lim)={ 10x=00<x9   Et nous avons besoin de demander ,C'est f ( n , 0 , f a l s e ) f(n, 0, false) f(n,0,false).
      Nous avons découvert, Si la solution est basée sur le transfert d'état ci - dessus , Peut causer un problème , C'est qu'il y a beaucoup de sous - problèmes qui se chevauchent. , Il faut donc se souvenir. , La façon la plus simple est d'utiliser un tableau tridimensionnel f [ n ] [ s t ] [ l i m ] f[n][st][lim] f[n][st][lim] Pour mémoriser .
      Bien sûr., Voici une technique ,C'est l i m lim lim Cette variable n'a que t r u e true true f a l s e false false Deux valeurs , Et quand il est f a l s e false false Heure, Représente le haut et l'intervalle désiré d'un nombre énuméré précédemment [ 0 , x ] [0, x] [0,x] Dans le paramètre droit x x x Les niveaux élevés de ,Donc quand l i m = f a l s e lim = false lim=false Heure, Les branches de l'arbre de recherche Deep First sont au plus 1 1 1 Article (s), Donc il n'y a pas besoin de mémoriser , Chaque fois que vous comptez directement . Comme le montre la figure 2. -3-2 Noeud bleu montré , C'est la seule branche. .
    Insérer la description de l'image ici
      En résumé,On a juste besoin de l'utiliser. f [ n ] [ s t ] f[n][st] f[n][st] Indique que la longueur est n n n, Et la plage de chaque nombre est [ 0 , m a x v ] [0, maxv] [0,maxv], Et l'état du préfixe est s t st st Nombre de chiffres (Ici. m a x v maxv maxv Lié au système décimal ,Si oui b b b Décimal,Alors m a x v = b − 1 maxv = b - 1 maxv=b1).
  • f ( n , s t , f a l s e ) f(n, st, false) f(n,st,false) Utiliser une recherche profonde commune , f ( n , s t , t r u e ) f(n, st, true) f(n,st,true) Recherche de mémoire .
       Pour les chiffres plus profonds DPRéalisation,Peut être référencé:.Algorithme d'écriture silencieuse tard dans la nuit(29.)- NumériqueDP.

Dix、Compression de l'étatDP

  Donner g r a p h graph graph Oui. n ( n ≤ 12 ) n(n \le 12) n(n12) Noeuds(Le numéro est 0, 1, 2, …, n − 1 n-1 n1) Graphique non rectiligne connecté de . g r a p h . l e n g t h = n graph.length = n graph.length=n, Et seulement les noeuds i i i Et j j j Quand connecté , j j j Pas égal à i i i Et dans la Liste g r a p h [ i ] graph[i] graph[i] Se produit exactement une fois dans . Renvoie la longueur du chemin le plus court qui peut accéder à tous les noeuds . Peut être à n'importe quel noeud C'est parti. Et Fin,C'est possible. Noeud de visite multiple ,Et ça pourrait Réutiliser les bords .

   C'est un accès répétable Questions des voyagistes. Nous pouvons concevoir l'état suivant : f ( s t , e n , s t a t e ) f(st, en, state) f(st,en,state) Représentant de s t st st À e n en en,Et Noeuds passés La combinaison d'états pour s t a t e state state Le chemin le plus court vers.
   La combinaison d'états signifie : Un nombre compressé binaire ,Par exemple, Noeuds passés Pour 0、1、4,Et s t a t e state state La représentation binaire de : ( 10011 ) 2 (10011)_2 (10011)2 C'est - à - dire: Noeuds passés Correspond à l'état s t a t e state state Le BIT de la représentation binaire est 1, Les autres bits sont 0.
  Et donc,, Nous définissons ce qui suit: :État initial、État final、 Statut illégal 、Statut intermédiaire.

État initial
  État initial On a dû trouver un point de départ. ,Imagine ça., Supposons que le point de départ soit i i i, Donc au début, ,Certainement. s t a t e = 2 i state = 2^i state=2i.Et donc,, Nous pouvons penser que le point de départ est i i i, La fin est i i i,L'état est 2 i 2^i 2i Le chemin le plus court pour 0. C'est - à - dire que l'état initial est exprimé comme suit: : f ( i , i , 2 i ) = 0   i ∈ [ 0 , n ) f(i, i, 2^i) = 0 \\ \ \\ i \in [0, n) f(i,i,2i)=0 i[0,n)

État final
   À cause de ce problème , Je ne nous l'ai pas dit. Point de départ Et Point final,Alors... Point de départ Et Point final C'est incertain., Nous devons le faire en énumérant , Donc l'état final Point de départ i i i Et Point final j j j,L'état est 2 n − 1 2^n-1 2n1( Ça veut dire que tous les points passent. , Chaque bit du binaire est 1). L'état final est exprimé comme suit: : f ( i , j , 2 n − 1 )   i ∈ [ 0 , n ) , j ∈ [ 0 , n ) f(i, j, 2^n-1) \\ \ \\ i \in [0, n), j \in [0, n) f(i,j,2n1) i[0,n),j[0,n)

Statut illégal
   Statut illégal C'est Impossible à partir de l'état initial Adoption Changement d'état État d'arrivée . Imaginons - le. ,Si f ( i , j , s t a t e ) f(i, j, state) f(i,j,state) Moyenne s t a t e state state Binaire de i i i Bitwise 0, Ou j j j Bits Pour 0, Cet état doit être illégal. , Il représente l'opposé de deux contradictions .
   Nous définissons le chemin le plus court dans un état illégal comme i n f = 10000000 inf = 10000000 inf=10000000 C'est tout.. f ( i , j , s t a t e ) = i n f f(i, j, state) = inf f(i,j,state)=inf
  Parmi eux (state & (1<<i)) == 0Ou(state & (1<<j)) == 0Représentantstate La représentation binaire de i i i Et j j j Non. 1.

Statut intermédiaire
   États autres que ceux mentionnés ci - dessus , Sont devenus intermédiaires .

  Alors,On peut passer par Recherche de mémoire,énumérer tous f ( i , j , 2 n − 1 ) f(i, j, 2^n - 1) f(i,j,2n1) De, Trouver un minimum est notre réponse. . Nombre de pays : O ( n 2 2 n ) O(n^22^n) O(n22n),Changement d'état: O ( n ) O(n) O(n),Complexité temporelle: O ( n 3 2 n ) O(n^32^n) O(n32n).

Onze、PenteDP

  Compte tenu de n ( n ≤ 400000 ) n(n \le 400000) n(n400000) Nombre a n a_n an, Ils doivent maintenant être classés , Au moins pour chaque catégorie t ( 1 < t ≤ n ) t(1 < t \le n) t(1<tn) Nombre. Les dépenses classées dans la même catégorie sont la somme de chaque chiffre moins le plus petit. . On s'attend à ce que le coût total de toutes les catégories soit le plus faible possible. , Trouver le coût minimum .

   D'abord avide. , Mettez - vous en ordre. .Et utiliser s u m [ i ] sum[i] sum[i] Avant de représenter i i i La somme des nombres,Parmi eux s u m [ 0 ] = 0 sum[0]=0 sum[0]=0, d p [ i ] dp[i] dp[i] Avant de représenter i i i Coût minimum après le classement des chiffres , Il est facile d'énumérer les équations de transition d'état :

   Parce que c'est ordonné. ,Alors... a [ j + 1 ] a[j+1] a[j+1] - Oui. a [ j + 1 : i ] a[j+1:i] a[j+1:i] Le plus petit nombre dans cet intervalle ,C'est un 1 D / 1 D 1D/1D 1D/1D Questions, C'est - à - dire que le nombre d'états est O ( n ) O(n) O(n), Les coûts de transfert par statut sont les suivants: O ( n ) O(n) O(n), Donc la complexité totale de l'algorithme est O ( n 2 ) O(n^2) O(n2). L'algorithme simple est le suivant: :

  Parce que n n n La plage est trop grande ,Besoin d'optimisation. L'essence de l'optimisation de l'algorithme est de laisser la boucle de première couche du code ci - dessus inchangée , Processus de transition de l'état pour réduire les cycles de deuxième niveau . Premièrement, l'équation de transfert d'état est déplacée , Obtenir l'équation suivante :

   Ça ne semble pas avoir changé. , Pourquoi faire ça? ? Regardez cette formule. :

  Un tel regard, En gros, vous pouvez comprendre la base de classification , Rouge signifie que l'argument est iFonction de, Vert signifie que l'argument est jFonction de, Le bleu est i i i Et j j j Est une fonction d'une variable , Alors nous allons faire une autre transformation , Rendre la formule plus claire .

  Oui. i i i Et j j j Pour les fonctions des arguments, utilisez bEtyReprésentation, k = i k=i k=i Pente représentative .Et donc,, L'équation de transfert d'état est convertie en a [ j + 1 ] a[j+1] a[j+1] Est un argument, i i i Est la pente , d p [ i ] − s u m [ i ] dp[i]-sum[i] dp[i]sum[i] Équation linéaire avec interception .

  Comme le montre la figure ci - dessus,Quand i i i C'est sûr., j j j Prends - le. t t t Heure, Représente une pente de i i i, Et un peu trop. T ( a [ t + 1 ] , d p [ t ] − s u m [ t ] + t ∗ a [ t + 1 ] ) T(a[t+1], dp[t]-sum[t]+t*a[t+1]) T(a[t+1],dp[t]sum[t]+ta[t+1]) Ligne droite.

   Plus généralement ,Quand i i i C'est sûr., j j j Lorsque différentes valeurs sont prises , Il y a une série de lignes parallèles dans ce plan. , Leurs pentes sont toutes i i i.Parce que i i i C'est sûr., Et la pente de toutes les lignes est i i i, Donc toutes les lignes sont parallèles ;Et parce que j j j La différence entre, La ligne traverse différents points , Donc, tant que deux lignes parallèles ne coïncident pas, , L'interception doit être différente , Et l'interception b = d p [ i ] − s u m [ i ] b=dp[i]-sum[i] b=dp[i]sum[i],C'est - à - dire: d p [ i ] = b + s u m [ i ] dp[i]=b+sum[i] dp[i]=b+sum[i]; On peut donc en conclure que :
  dp[i] La valeur minimale doit apparaître sur la ligne la plus basse ( Parce que la ligne la plus basse a la plus petite interception ).
  Et puis..., Nous analysons Quelques propriétés importantes :
  Article premier:Entretien“ Hyponvexe ” Ligne brisée

  Comme le montre la figure,A、B、CTrois points.,Parmi euxB Point à AC En ligne droite , C'est un “ Convexité supérieure ”Point. Et nous nous connectons ACDeux heures., Dessiner toutes les pentes inférieures à K(A,C)Ligne droite( Ligne verte dans l'image ), On a découvert que l'interception minimale devait être le point de passage. ALigne droite(Imagine ça., Trois lignes vertes se déplacent ensemble ); Puis dessinez toutes les pentes supérieures à K(A,C)Ligne droite( Ligne rouge dans l'image ), La plus petite interception doit passer. CLigne droite.Et donc,,On peut en tirer des conclusions.,En serviceA、B、C Lors du transfert d'état ,B Toujours un changement d'état inutile .
   Parce qu'aucun des trois points ne peut apparaître “ Convexité supérieure ”.Alors..., Tous les points utilisés pour le transfert d'état doivent être un “ Hyponvexe ” Ligne brisée ,Comme le montre la figure:
Insérer la description de l'image ici
   Chaque point du graphique représente la direction dp[i] Transfert d'état dp[j].Comme le montre la figure,“ Hyponvexe ” Les polylignes répondent à l'augmentation monotone de la pente de chaque segment . Comment maintenir cette section “ Hyponvexe ” Ligne brisée ?
   Nous utilisons une file d'attente à deux extrémités pour la maintenance , En raison de la monotonie de sa structure de stockage ( Pente monotone ),Aussi appelé“File d'attente monotone”.deq[] Champ de données représentant une file d'attente monotone ,headEttail Les deux pointeurs qui le représentent ,Quand headEttail égal signifie que la file d'attente monotone est vide ,Initialisationhead=tail=0.deq[] Chaque élément contient un indice du tableau original , Parce que vous pouvez calculer le point médian x-yCoordonnées, Vous pouvez calculer la pente entre deux points adjacents. .
   Donc chaque fois que nous avons un état de transition viable j Avant de mettre dans une file d'attente monotone , On peut d'abord déterminer si son addition peut assurer une augmentation monotone de la pente. , Si ce n'est pas le cas, supprimer l'élément de queue de file d'attente monotone , À tour de rôle. , Enfin, placez ce point à la fin de la file d'attente monotone , Comme ça. “ Hyponvexe ” La ligne brisée est réparée. .
   Lecteurs attentifs , Vous verrez que cette étape fonctionne également “Pile” Cette structure de données complète .Et puis..., Passons à la raison pour laquelle les files d'attente à deux extrémités n'ont pas besoin de piles. .
  Article 2:“ Ne jamais embaucher ” Élimination des points
  “ Ne jamais embaucher ” C'est mon nom. , Quels sont les points? “ Ne jamais embaucher ”Point?, Ou regarder la photo :
Insérer la description de l'image ici
   Parce que chaque état énuméré i Est une énumération incrémentale ( Le premier du Code précédent forCycle), Ce qui signifie que la pente doit augmenter , Donc, comme vous pouvez le voir, , Ces pentes sont inférieures à i Point sur la polyligne de ( Point gris ) Si vous passez par une pente de iLigne droite( Ligne parallèle de la Ligne verte dans l'image ), L'interception ne doit pas être plus petite que la Ligne verte , Les points gris peuvent être supprimés. .
   Ces points gris qui peuvent être supprimés sont “ Ne jamais embaucher ”Point.“ Ne jamais embaucher ” Plus officiellement. , Dans une file d'attente monotone. , Toutes les pentes sont inférieures à i Point d'extrémité gauche de la polyligne . En raison de la monotonie de pente des files d'attente monotones , Ainsi, vous pouvez supprimer des points de gauche à droite , C'est pourquoi la pile n'a pas été utilisée pour la maintenance. . Si la pile est utilisée pour maintenir la polyligne , Le point le plus à gauche doit être au bas de la pile. , La pile n'obtient que l'élément supérieur de la pile .

Douze、ConnectivitéDP

   Je ne pense pas que tu puisses voir ça non plus. ,Si vous voyez ici, Alors s'il vous plaît, dites quelque chose dans la section commentaires :“Je vois.!”.Je ne peux que le dire.:J'ai été précipité..
  Ça devrait être ACM Le problème de programmation dynamique le plus difficile , J'ai donc l'intention de consacrer un article à ce sujet. ,Ne t'inquiète pas, L'entrevue sur le lieu de travail n'est certainement pas un test , Si vous réussissez l'examen, , L'intervieweur a dû essayer de faire un spectacle. .


  À propos de 「 Planification dynamique 」 C'est fini ici.
  S'il y a des questions que je ne comprends pas,Peut passer 「 Page d'accueil de l'édition informatique 」Trouver l'auteur「 Coordonnées 」 ,Communication en ligne.


  ConcernantDessiner la structure des donnéesToutes les sources sont open source,Liens ci - dessous:《Dessiner la structure des données》



  Je crois que la plupart de mes articles sont「 Étudiants 」,Tous ceux qui peuvent aller à l'Université sont「 Elite 」,Alors naturellement, nous devons「 L'excellence 」,Si vous êtes toujours「 Première année 」,C'est super,Tu as beaucoup de temps,Bien sûr que tu as le choix.「 Drama de brosse 」,Et pourtant,「 Apprendre les algorithmes 」,Trois ans plus tard, vous serez naturellement「 On ne peut pas parler en même temps 」.
  Alors, ici.,J'ai rangé「 Des dizaines d'algorithmes de base 」 Classification de,Cliquez pour ouvrir:

Guide de démarrage de l'algorithme

  Si le lien est masqué,Ou avoir des problèmes de permission,On peut parler à l'auteur.
  Aperçu de l'ensemble de questions:


Insérer la description de l'image ici


  Pour rendre ça intéressant,Et 「 Prendre soin des débutants 」,À l'heure actuelle, seuls les algorithmes les plus simples sont ouverts 「 Série ENUM 」 (Y compris:: énumération linéaire、Double pointeur、Préfixe et、Dénombrement binaire、Dénombrement trigonométrique),Oui. La moitié des membres ont fini. 「 Série ENUM 」 Après toutes les questions,Ouvre le chapitre suivant,Quand tout sera fini.,Tu es toujours dans le Groupe.,Alors tu seras 「 .Algorithme d'écriture silencieuse tard dans la nuit 」Groupe d & apos; experts Un membre de.
  Ne sous - estimez pas ce groupe d'experts,Trois ans plus tard,Tu seras quelqu'un d'autre. C'est impossible. L'existence de.Si vous voulez rejoindre,Vous pouvez me contacter,Vu que tout le monde est étudiant, Non.「 Principales sources économiques 」,Sur le chemin de devenir Dieu, 「 Je ne demande rien. 」.

Il n'y a pas d'algorithmes difficiles à apprendre

CTutoriels d'animation gratuits en langue,Frappe avec moi!
La photoastronomieCLangues

Niveau d'entréeCRésumé des vrais problèmes linguistiques
🧡《CIntroduction à la langue100Exemple》🧡

Quelques diagrammes apprennent une structure de données
Dessiner la structure des données

Apprentissage en groupe,Croissance de la masse
Guide de démarrage de l'algorithme

Tutoriel d'images et de textes de la médaille d'or du concurrent
.Algorithme d'écriture silencieuse tard dans la nuit

Avantages exclusifs pour les fans

Introduction à la langue(Base)《La photoastronomieCLangues》 Exemple de résolution complète du Code
Formation linguistique (Niveau avancé)《CIntroduction à la langue100Exemple》Version Hardcover
Structure des données(L'Université)《Dessiner la structure des données》Code source
Introduction aux algorithmes(Lieu de travail)《Introduction aux algorithmes》 Orientation
Algorithme avancé (Concours)《.Algorithme d'écriture silencieuse tard dans la nuit》Modèle d'algorithme

   Le Code de vérification peut être obtenu à partir du numéro d'entreprise . S'il y a de l'école, 、Concours、 Problèmes sur le lieu de travail , Et plus encore ,C'est bon. 「 Une conversation privée. 」Auteur,Ou par「 Page d'accueil de l'ordinateur à gauche 」 Trouver l'auteur 「 Coordonnées 」 Discussion sur la communication .
   Si vous êtes satisfait :
   ( 1 ) (1) (1) Il y a un fort désir. 「 Pour bien apprendreCLangues 」De
   ( 2 ) (2) (2) Il y a un fort désir. 「 Pour bien apprendreC++ 」De
   ( 3 ) (3) (3) Il y a un fort désir. 「 Pour bien apprendre la structure des données 」De
   ( 4 ) (4) (4) Il y a un fort désir. 「 Pour bien apprendre les algorithmes 」De
   ( 5 ) (5) (5) Il y a un fort désir. 「 Je veux entrer dans une grande usine. 」De
   Si vous êtes satisfait de l'un des points ci - dessus ,Alors, Nous sommes des gens aux vues similaires. !
  Contacter l'auteur,Ou scanner la page d'accueil de l'auteur Code QR plus Groupe, Rejoignez - nous.

版权声明
本文为[Où est le héros?]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/09/20210905100446047H.html