이 기사에서 우리는 이 기사의 K-ary 트리에서 가중치 W 경로의 수를 계산하기 위해 C++를 사용할 것입니다. 각 노드에 K개의 자식이 있고 각 모서리에 가중치가 할당되어 있는 트리인 K-ary 트리를 제공했습니다. 가중치는 한 노드에서 모든 자식까지 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와 같을 경우 경로의 총 가중치를 계산했습니다.
답을 1씩 증가시키고 해당 경로를 방문한 것으로 표시하고 가능한 모든 경로를 계속 진행하고 가중치가 M보다 크거나 같은 모서리를 하나 이상 포함합니다.
결론
이 기사에서는 O(W*K)의 동적 계획법을 사용하여 k-ary 트리에서 가중치가 W인 경로의 수를 찾는 문제를 풉니다. 시간 복잡도.
우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하기 위한 완전한 접근 방식(Normal 및 Efficiency)을 배웠습니다.