Trouver le nombre de chemins de poids W dans un arbre K-ary en utilisant C++

Dans cet article, nous utiliserons C++ pour compter le nombre de chemins de poids W dans un arbre K-ary. On nous a donné un arbre K-ary, qui est un arbre dans lequel chaque nœud a K enfants et chaque arête a un poids, le poids décroissant de 1 à K d'un nœud à tous ses enfants.

Nous devons compter le nombre cumulé de chemins partant du nœud racine qui ont un poids W et au moins une arête de poids M. Voici donc un exemple :

Input : W = 4, K = 3, M = 2

Output : 6

Dans le problème donné, nous utiliserons dp pour réduire la complexité temporelle et spatiale. En utilisant la mémorisation, nous pouvons rendre nos programmes plus rapides et les adapter à des contraintes plus larges.

Méthode

Dans cette méthode, nous allons parcourir l'arbre et garder une trace des arêtes avec ou sans poids d'au moins M et poids égal à W, puis nous incrémentons la réponse.

Input

#include <bits/stdc++.h>
using namespace std;
int solve(int DP[][2], int W, int K, int M, int used){
   if (W < 0) // if W becomes less than 0 then return 0
       return 0;
    if (W == 0) {
        if (used) // if used is not zero then return 1
           return 1; //as at least one edge of weight M is included
       return 0;
   }
    if (DP[W][used] != -1) // if DP[W][used] is not -1 so that means it has been visited.
       return DP[W][used];
    int answer = 0;
   for (int i = 1; i <= K; i++) {
        if (i >= M)
           answer += solve(DP, W - i, K, M, used | 1); // if the condition is true
                                                    //then we will change used to 1.
       else
           answer += solve(DP, W - i, K, M, used);
   }
   return answer;
}
int main(){
   int W = 3; // weight.
   int K = 3; // the number of children a node has.
   int M = 2; // we need to include an edge with weight at least 2.
   int DP[W + 1][2]; // the DP array which will
   memset(DP, -1, sizeof(DP)); // initializing the array with -1 value
   cout << solve(DP, W, K, M, 0) << "\n";
   return 0;
}

Output

3

Explication du code ci-dessus

Dans cette méthode, les arêtes de poids M sont incluses au moins une fois ou non. Deuxièmement, nous avons calculé le poids total du chemin s’il est égal à W.

Nous incrémentons la réponse de un, marquons le chemin comme visité, continuons à travers tous les chemins possibles et contenons au moins une arête avec un poids supérieur ou égal à M.

Conclusion

Dans cet article, nous avons utilisé la programmation dynamique pour résoudre le problème de la recherche du nombre de chemins de poids W dans un arbre k-ary avec une complexité temporelle de O(W*K).

Nous avons également appris un programme C++ et une méthode complète (commune et efficace) pour résoudre ce problème.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!