इस आलेख में, हम इस आलेख में K-ary ट्री में वज़न W पथों की संख्या की गणना करने के लिए C++ का उपयोग करेंगे। हमने एक K-ary पेड़ दिया है, जो एक ऐसा पेड़ है जिसमें प्रत्येक नोड में K बच्चे होते हैं और प्रत्येक किनारे को एक भार सौंपा जाता है, जिसका वज़न एक नोड से K तक उतरते हुए उसके सभी बच्चों के लिए होता है।
हमें रूट से शुरू होने वाले पथों की संचयी संख्या की गणना करने की आवश्यकता है जिनका वजन डब्ल्यू और कम से कम एक किनारे एम के वजन के साथ है। तो, यहां उदाहरण है -
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
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, वजन के किसी भी किनारे का ट्रैक रखते हुए, एम को कम से कम एक बार शामिल किया जाता है या नहीं। दूसरे, हमने पथ के कुल भार की गणना की यदि यह W के बराबर हो जाता है।
हम उत्तर को एक से बढ़ाते हैं, उस पथ को विज़िट किया गया के रूप में चिह्नित करते हैं, सभी संभावित पथों के माध्यम से जारी रखते हैं, और कम से कम एक किनारे को M से अधिक या उसके बराबर वजन के साथ शामिल करते हैं।
निष्कर्ष
इस लेख में, हम O(W*K) में डायनेमिक प्रोग्रामिंग का उपयोग करके k-ary ट्री में वज़न W वाले पथों की संख्या ज्ञात करने के लिए एक समस्या का समाधान करते हैं समय जटिलता।
हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (सामान्य और कुशल) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया।