Ermitteln Sie mit C++ die Anzahl der Pfade mit der Gewichtung W in einem K-ary-Baum

In diesem Artikel verwenden wir C++, um die Anzahl der Pfade mit der Gewichtung W in einem K-ary-Baum zu zählen. Uns wurde ein K-ary-Baum gegeben, ein Baum, in dem jeder Knoten K Kinder hat und jede Kante ein Gewicht hat, wobei das Gewicht von 1 auf K von einem Knoten zu allen seinen Kindern abnimmt.

Wir müssen die kumulative Anzahl der Pfade zählen, die vom Wurzelknoten beginnen und die Gewichtung W und mindestens eine Kante mit der Gewichtung M haben. Hier ist ein Beispiel:

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

Output : 6

Im gegebenen Problem werden wir dp verwenden, um die zeitliche und räumliche Komplexität zu reduzieren. Durch die Memoisierung können wir unsere Programme schneller machen und sie an größere Einschränkungen anpassen.

Methode

Bei dieser Methode durchqueren wir den Baum und verfolgen Kanten mit oder ohne Gewicht von mindestens M und einem Gewicht gleich W und erhöhen dann die Antwort.

Eingabe

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

Ausgabe

3

Erklärung des obigen Codes

Bei dieser Methode werden Kanten mit dem Gewicht M mindestens einmal einbezogen oder nicht. Zweitens haben wir das Gesamtgewicht des Pfades berechnet, wenn es gleich W ist.

Wir erhöhen die Antwort um eins, markieren den Pfad als besucht, fahren mit allen möglichen Pfaden fort und enthalten mindestens eine Kante mit einem Gewicht größer oder gleich M.

Fazit

In diesem Artikel haben wir dynamische Programmierung verwendet, um das Problem zu lösen, die Anzahl der Pfade mit dem Gewicht W in einem k-ary-Baum mit einer zeitlichen Komplexität von O(W*K) zu finden.

Wir haben auch ein C++-Programm und eine vollständige Methode (allgemein und effizient) gelernt, um dieses Problem zu lösen.

Das obige ist der detaillierte Inhalt vonErmitteln Sie mit C++ die Anzahl der Pfade mit der Gewichtung W in einem K-ary-Baum. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!