এই নিবন্ধে, আমরা এই নিবন্ধে K-ary গাছের ওজন W পাথের সংখ্যা গণনা করতে C++ ব্যবহার করব। আমরা একটি কে-আরি ট্রি দিয়েছি, এটি এমন একটি গাছ যেখানে প্রতিটি নোডের কে শিশু রয়েছে এবং প্রতিটি প্রান্তের একটি ওজন নির্ধারণ করা হয়েছে, যার ওজন একটি নোড থেকে তার সমস্ত বাচ্চাদের জন্য 1 থেকে কে পর্যন্ত নেমে আসে৷
আমাদের মূল থেকে শুরু হওয়া পাথের ক্রমবর্ধমান সংখ্যা গণনা করতে হবে যার ওজন 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) // 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)-এ ডাইনামিক প্রোগ্রামিং ব্যবহার করে কে-আরি গাছে ওজন সহ পাথের সংখ্যা খুঁজে পেতে একটি সমস্যার সমাধান করি। সময় জটিলতা।
আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ এবং দক্ষ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি।
