इस लेख में, हम C++ का उपयोग करके K-ary ट्री में वजन W वाले पथों की संख्या की गणना करेंगे। हमें एक K-ary ट्री दिया गया है, जो एक ऐसा ट्री है जिसमें प्रत्येक नोड के K चाइल्ड होते हैं और प्रत्येक एज को एक वजन दिया गया है, जिसमें एक नोड से इसके सभी चाइल्ड तक वजन 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) // यदि W 0 से कम हो जाए तो 0 लौटाएं return 0; if (W == 0) { if (used) // यदि used शून्य नहीं है तो 1 लौटाएं return 1; // क्योंकि कम से कम M वजन की एक एज शामिल है return 0; } if (DP[W][used] != -1) // यदि DP[W][used] -1 नहीं है तो इसका मतलब है इसे विज़िट किया गया है 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); // यदि शर्त सत्य है // तो हम used को 1 में बदल देंगे else answer += solve(DP, W - i, K, M, used); } return answer; } int main(){ int W = 3; // वजन int K = 3; // एक नोड के चाइल्ड की संख्या int M = 2; // हमें कम से कम 2 वजन की एज शामिल करने की आवश्यकता है int DP[W + 1][2]; // DP सरणी जो memset(DP, -1, sizeof(DP)); // सरणी को -1 मान से आरंभ करना cout << solve(DP, W, K, M, 0) << "\n"; return 0; }आउटपुट
3
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, किसी भी एज के वजन M को कम से कम एक बार शामिल किया गया है या नहीं, इसका ट्रैक रखा जाता है। दूसरे, हमने पथ के कुल वजन की गणना की यदि यह W के बराबर हो जाता है।
हम उत्तर को एक से बढ़ाते हैं, उस पथ को विज़िटेड के रूप में चिह्नित करते हैं, सभी संभावित पथों के माध्यम से जारी रखते हैं, और कम से कम M वजन वाली एक एज शामिल करते हैं।
निष्कर्ष
इस लेख में, हम डायनामिक प्रोग्रामिंग का उपयोग करके K-ary ट्री में वजन W वाले पथों की संख्या O(W*K) समय जटिलता में ज्ञात करने की समस्या को हल करते हैं।
हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण (सामान्य और कुशल) भी सीखा जिससे हमने इस समस्या को हल किया।
