数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 查找 K 叉树中权重为 W 的路径数
在这篇文章中，我们将使用 C++ 来计算这篇文章中 K 叉树中权重为 W 的路径数。我们给定了一个 K 叉树，它是一棵每个节点有 K 个子节点的树，并且每条边都分配了一个权重，权重从一个节点到其所有子节点依次递减从 1 到 K。
我们需要计算从根节点开始的、权重为 W 且至少有一条权重为 M 的边的路径的总数。因此，这是一个示例 -
Input : W = 4, K = 3, M = 2 Output : 6
在给定的问题中，我们将使用 dp 来减少我们的时间和空间复杂度。通过使用记忆化，我们可以使我们的程序更快，并使其适用于更大的约束条件。
方法
在这种方法中，我们将遍历树并跟踪是否使用了至少权重为 M 的边，以及权重是否等于 W，然后我们将答案加 1。
输入
#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 叉树中权重为 W 的路径数。
我们还学习了这个问题的 C++ 程序以及我们解决这个问题的完整方法（普通和高效）。
更新于: 2021-11-24
138 次浏览
广告