এই টিউটোরিয়ালে, আমরা বাইনারি ট্রিতে নোডের সর্বাধিক যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব যাতে ডায়নামিক প্রোগ্রামিং ব্যবহার করে কোন দুটি সংলগ্ন না হয়।
এর জন্য আমাদের একটি বাইনারি গাছ দেওয়া হবে। আমাদের কাজ হল সর্বাধিক যোগফল সহ উপসেট খুঁজে বের করা যাতে উপসেটের কোন দুটি নোড ডাইনামিক প্রোগ্রামিং ব্যবহার করে সরাসরি সংযুক্ত থাকে না।
উদাহরণ
#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
