এই আর্টিকেলে আমরা C++ ব্যবহার করে K-ary Tree-এ ওজন W वाले পথ সংখ্যা বের করব। আমাদের কাছে একটি K-ary Tree আছে, যেটি এমন একটি ট্রি যেখানে প্রতিটি নোডের Kটি চাইল্ড থাকে এবং প্রতিটি এজের একটি ওজন নির্ধারিত থাকে, একটি নোড থেকে তার সকল চাইল্ড পর্যন্ত ওজন ১ থেকে K পর্যন্ত হয়।
আমাদের কাজ হল রুট থেকে শুরু হওয়া ওজন W वाले পথের মোট সংখ্যা বের করা যাতে কমপক্ষে একটি এজ থাকে যার ওজন M। উদাহরণ:
ইনপুট : W = 4, K = 3, M = 2 আউটপুট : 6
দেওয়া সমস্যায় আমরা DP (ডাইনামিক প্রোগ্রামিং) ব্যবহার করব আমাদের সময় এবং স্পেস জটিলতা কমাতে। মেমোইজেশন ব্যবহার করে আমরা প্রোগ্রামটি অনেক দ্রুত করতে পারি এবং বড় কনস্ট্রেইন্টের জন্য ব্যবহার যোগ্য করতে পারি।
পদ্ধতি
এই পদ্ধতিতে আমরা ট্রি traverser করব এবং ট্র্যাক রাখব কমপক্ষে 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 ০-এর চেয়ে কম হয় তবে ০ রিটার্ন return 0; if (W == 0) { if (used) // যদি used শূন্য না হয় তবে ১ রিটার্ন 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 ১ করব else answer += solve(DP, W - i, K, M, used); } return answer; } int main(){ int W = 3; // ওজন int K = 3; // প্রতিটি নোডের চাইল্ড সংখ্যা int M = 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-এর সমান হয়, তবে আউটপুট এক বাড়ানো হয়, সেই পথকে ভিজিটেড মার্ক করে, সকল সম্ভাব্য পথ traverser করা হয় এবং কমপক্ষে একটি M বা তার চেয়ে বড় ওজনোর এজ অন্তর্ভুক্ত করা হয়।
উপসংহার
এই আর্টিকেলে আমরা ডাইনামিক প্রোগ্রামিং ব্যবহার করে K-ary Tree-এ ওজন W वाले পথ সংখ্যা O(W*K) সময় জটিলতায় বের করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সমাধানের পূর্ণ পদ্ধতি (সাধারণ এবং দক্ষ) শিখেছি।
