Trong bài viết này, chúng tôi sẽ sử dụng C ++ để tính số lượng đường dẫn W trọng số trong cây K-ary trong bài viết này. Chúng tôi đã đưa ra cây K-ary, là cây trong đó mỗi nút có K con và mỗi cạnh có trọng số được gán cho nó, với trọng số giảm dần từ 1 đến K từ một nút cho tất cả các nút con của nó.
Chúng ta cần đếm số lượng tích lũy các đường đi bắt đầu từ gốc có trọng lượng là W và ít nhất một cạnh có trọng số là M. Vì vậy, đây là ví dụ -
Input : W = 4, K = 3, M = 2 Output : 6
Trong bài toán đã cho, chúng ta sẽ sử dụng dp để giảm độ phức tạp về thời gian và không gian của chúng ta. Bằng cách sử dụng ghi nhớ, chúng tôi có thể làm cho chương trình của mình nhanh hơn nhiều và làm cho nó có thể sử dụng được cho các ràng buộc lớn hơn.
Phương pháp tiếp cận
Trong cách tiếp cận này, chúng tôi sẽ đi ngang qua cây và theo dõi cạnh có trọng số ít nhất là M nếu được sử dụng hay không, và trọng số bằng W, vì vậy chúng tôi tăng câu trả lời.
Đầu vào
#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;
} Đầu ra
3
Giải thích về Quy tắc trên
Trong cách tiếp cận này, theo dõi bất kỳ cạnh trọng lượng nào, M có được đưa vào ít nhất một lần hay không. Thứ hai, chúng tôi đã tính toán tổng trọng lượng của đường dẫn nếu nó trở nên bằng W.
Chúng tôi tăng dần câu trả lời lên từng đường một, đánh dấu đường dẫn đó là đã truy cập, tiếp tục qua tất cả các đường có thể và bao gồm ít nhất một cạnh có trọng số lớn hơn hoặc bằng M.
Kết luận
Trong bài viết này, chúng tôi giải quyết vấn đề tìm số lượng đường đi có trọng số W trong cây k-ary bằng cách sử dụng lập trình động trong O (W * K) phức tạp về thời gian.
Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này.