C ++を使用して、K-aryツリー内の重みWのパスの数を見つけます

この記事では、C ++を使用して、この記事のK-aryツリー内の重みWパスの数を計算します。 K-aryツリーを指定しました。これは、各ノードにK個の子があり、各エッジに重みが割り当てられており、重みは1つのノードからすべての子に1からKまで下がっています。

重みがWで、重みがMのエッジが少なくとも1つある、ルートから始まるパスの累積数をカウントする必要があります。したがって、ここに例-

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が少なくとも1回含まれるかどうかに関係なく含まれます。次に、パスがWに等しくなった場合のパスの総重量を計算しました。

回答を1つ増やし、そのパスを訪問済みとしてマークし、可能なすべてのパスを続行し、重みがM以上のエッジを少なくとも1つ含めます。

結論

この記事では、 O（W * K）の動的計画法を使用して、k-aryツリー内の重みWのパスの数を見つける問題を解決します。 時間計算量。

また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常および効率的）についても学びました。