資料結構
網路
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 次瀏覽
廣告