C++ を使用して、K 進木で重み W を持つパスの数を求めます。

この記事では、C を使用して、K 進木内の重み W を持つパスの数を数えます。 K 進木が与えられました。これは、各ノードが K 個の子を持ち、各エッジが重みを持ち、ノードからそのすべての子に向かって重みが 1 から K に減少する木です。

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

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

Output : 6

与えられた問題では、時間と空間の複雑さを軽減するために dp を使用します。メモ化を使用すると、プログラムを高速化し、より大きな制約に適応させることができます。

メソッド

このメソッドでは、ツリーを走査し、少なくとも M の重みと W に等しい重みの有無にかかわらずエッジを追跡し、その後、答えをインクリメントします。

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

上記コードの説明

このメソッドでは、重み M のエッジが少なくとも 1 回含まれるか含まれません。次に、パスが W に等しい場合のパスの合計の重みを計算しました。

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

結論

この記事では、動的計画法を使用して、時間計算量 O で、k 分木内の重み W のパスの数を見つける問題を解決します。 (W*K)。

私たちは、C プログラムと、この問題を解決するための完全な方法 (一般的で効率的) も学びました。

以上がC++ を使用して、K 進木で重み W を持つパスの数を求めます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。