बाइनरी ट्री में नोड्स का अधिकतम योग जैसे कि कोई भी दो आसन्न न हो | सी ++ में गतिशील प्रोग्रामिंग

इस ट्यूटोरियल में, हम बाइनरी ट्री में नोड्स के अधिकतम योग को खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे, ताकि कोई भी दो डायनामिक प्रोग्रामिंग का उपयोग करके आसन्न न हो।

इसके लिए हमें एक बाइनरी ट्री प्रदान किया जाएगा। हमारा कार्य अधिकतम योग वाले उपसमुच्चय को इस प्रकार खोजना है कि उपसमुच्चय में कोई भी दो नोड डायनेमिक प्रोग्रामिंग का उपयोग करके सीधे जुड़े न हों।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
//finding diameter using dynamic programming
void dfs(int node, int parent, int dp1[], int dp2[], list<int>* adj, int tree[]){
   int sum1 = 0, sum2 = 0;
   for (auto i = adj[node].begin(); i != adj[node].end();
      ++i) {
         if (*i == parent)
            continue;
         dfs(*i, node, dp1, dp2, adj, tree);
         sum1 += dp2[*i];
         sum2 += max(dp1[*i], dp2[*i]);
      }
      dp1[node] = tree[node] + sum1;
      dp2[node] = sum2;
}
int main() {
   int n = 5;
   list<int>* adj = new list<int>[n + 1];
   adj[1].push_back(2);
   adj[2].push_back(1);
   adj[1].push_back(3);
   adj[3].push_back(1);
   adj[2].push_back(4);
   adj[4].push_back(2);
   adj[2].push_back(5);
   adj[5].push_back(2);
   int tree[n + 1];
   tree[1] = 10;
   tree[2] = 5;
   tree[3] = 11;
   tree[4] = 6;
   tree[5] = 8;
   int dp1[n + 1], dp2[n + 1];
   memset(dp1, 0, sizeof dp1);
   memset(dp2, 0, sizeof dp2);
   dfs(1, 1, dp1, dp2, adj, tree);
   cout << "Maximum sum: " << max(dp1[1], dp2[1]) << endl;
   return 0;
}

आउटपुट

Maximum sum: 25