使用C++找到K叉樹中權重為W的路徑數

在本文中，我們將使用C 來計算K叉樹中權重為W的路徑數。我們已經給了一個K叉樹，它是一棵每個節點有K個子節點且每條邊都有一個權重的樹，權重從1到K遞減從一個節點到其所有子節點。

我們需要計算從根節點開始的累積路徑數，這些路徑具有權重為W且至少有一條邊的權重為M。所以，這是一個例子：

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

Output : 6

在給定的問題中，我們將使用dp來減少時間和空間複雜度。透過使用記憶化，我們可以使我們的程序更快，並使其適用於更大的約束。

方法

在這個方法中，我們將遍歷樹，並追蹤使用或不使用至少為M的權重的邊，且權重等於W，然後我們增加答案。

輸入

#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;
}

輸出

3

上述程式碼的解釋

在這種方法中，至少包含一次或不包含任何權重為M的邊。其次，我們計算了路徑的總權重，如果它等於W。

我們將答案增加一，將該路徑標記為已訪問，繼續通過所有可能的路徑，並至少包含一條權重大於或等於M的邊。

結論

在本文中，我們使用動態規劃解決了在k叉樹中找到權重為W的路徑數的問題，時間複雜度為O(W*K )。

我們也學習了解決這個問題的C 程式和完整的方法（普通和高效）。

以上是使用C++找到K叉樹中權重為W的路徑數的詳細內容。更多資訊請關注PHP中文網其他相關文章！