Find the number of paths with weight W in a K-ary tree using C++

In this article, we will use C to count the number of paths with weight W in the K-ary tree. We have been given a K-ary tree, which is a tree in which each node has K children and each edge has a weight, with the weight decreasing from 1 to K from a node to all its children.

We need to count the cumulative number of paths starting from the root node that have weight W and at least one edge with weight M. So, here is an example:

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

Output : 6

In the given problem, we will use dp to reduce the time and space complexity. By using memoization, we can make our programs faster and adapt them to larger constraints.

Method

In this method we will traverse the tree and keep track of edges with or without weight of at least M and weight equal to W, then we increment the answer.

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

Explanation of the above code

In this method, edges with weight M are included at least once or not . Second, we calculated the total weight of the path if it is equal to W.

We increment the answer by one, mark the path as visited, continue through all possible paths, and contain at least one edge with weight greater than or equal to M.

Conclusion

In this article, we use dynamic programming to solve the problem of finding the number of paths with weight W in a k-ary tree, with a time complexity of O(W*K ).

We also learned the C program and the complete method (common and efficient) to solve this problem.

The above is the detailed content of Find the number of paths with weight W in a K-ary tree using C++. For more information, please follow other related articles on the PHP Chinese website!