C++를 사용하여 K-ary 트리에서 가중치가 W인 경로 수 찾기

이 기사에서는 C++를 사용하여 K-ary 트리에서 가중치 W를 갖는 경로 수를 계산합니다. K-진 트리는 각 노드에 K개의 자식이 있고 각 가장자리에 가중치가 있으며 노드에서 모든 자식까지 가중치가 1에서 K로 감소하는 트리입니다.

가중치 W가 있고 가중치 M이 있는 최소 하나의 가장자리가 있는 루트 노드에서 시작하여 누적 경로 수를 계산해야 합니다. 예를 들면 다음과 같습니다.

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

Output : 6

주어진 문제에서 dp를 사용하여 시간과 공간의 복잡성을 줄입니다. 메모이제이션을 사용하면 프로그램을 더 빠르게 만들고 더 큰 제약 조건에 맞게 조정할 수 있습니다.

Method

이 방법에서는 트리를 순회하고 가중치가 최소 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을 갖는 모든 모서리가 적어도 한 번 포함되거나 포함되지 않습니다. 둘째, W와 같을 경우 경로의 총 가중치를 계산했습니다.

답을 1씩 증가시키고, 경로를 방문한 것으로 표시하고, 가능한 모든 경로를 계속 진행하며, 가중치가 M보다 크거나 같은 간선을 하나 이상 포함합니다.

결론

이 논문에서는 시간 복잡도가 O(W*K)인 k-진 트리에서 가중치가 W인 경로 수를 찾는 문제를 동적 프로그래밍을 사용하여 해결했습니다.

우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 완전한 방법(일반적이고 효율적인)을 배웠습니다.

위 내용은 C++를 사용하여 K-ary 트리에서 가중치가 W인 경로 수 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!