সমস্যা বিবৃতি
একটি অ্যারে দেওয়া হলে, আমরা সংখ্যার একটি সারি A কে সর্বাধিক K সংলগ্ন (খালি নয়) গোষ্ঠীতে বিভক্ত করি, তারপর স্কোর হল প্রতিটি গ্রুপের গড়ের সমষ্টি। সর্বোচ্চ কত স্কোর করা যায়?
উদাহরণ
যদি ইনপুট অ্যারে হয় {9, 2, 5, 3, 10} তাহলে আমরা নিচের মতো অ্যারে পার্টিশন করতে পারি -
{9} {2, 5, 3} এবং {10} তাহলে এর গড় যোগফল −
9 + (2 + 5 + 3)/ 3 + 10 =22.33
অ্যালগরিদম
এই সমস্যাটি সমাধান করতে আমরা মুখস্থ কৌশল ব্যবহার করতে পারি -
- অধিকাংশ K অংশে A[i থেকে n-1] ভাগ করে মেমো[i][k] সেরা স্কোর হতে দিন
- প্রথম গ্রুপে, আমরা A[i থেকে n-1] কে A[i থেকে j-1] এবং A[j থেকে n-1] তে বিভাজন করি, তারপরে আমাদের প্রার্থী পার্টিশনের স্কোর গড় (i, j) + স্কোর(j, k-1)), যেখানে গড়(i, j) =(A[i] + A[i+1] + … + A[j-1]) / (j - i)। আমরা এর মধ্যে সর্বোচ্চ স্কোর নিই
- সাধারণ ক্ষেত্রে আমাদের পুনরাবৃত্তি হল :memo[n][k] =সর্বোচ্চ(মেমো[n][k], স্কোর(মেমো, i, A, k-1) + গড়(i, j) ))
উদাহরণ
আসুন এখন একটি উদাহরণ দেখি -
#include <bits/stdc++.h> using namespace std; define MAX 1000 double memo[MAX][MAX]; double score(int n, vector<int>& arr, int k) { if (memo[n][k] > 0) { return memo[n][k]; } double sum = 0; for (int i = n - 1; i > 0; i--) { sum += arr[i]; memo[n][k] = max(memo[n][k], score(i, arr, k - 1) + sum / (n - i)); } return memo[n][k]; } double getLargestSum(vector<int>& arr, int K) { int n = arr.size(); double sum = 0; memset(memo, 0.0, sizeof(memo)); for (int i = 0; i < n; i++) { sum += arr[i]; memo[i + 1][1] = sum / (i + 1); } return score(n, arr, K); } int main() { vector<int> arr = {9, 2, 5, 3, 10}; int K = 3; cout << "Largest sum = " << getLargestSum(arr, K) << endl; return 0; }
আউটপুট
আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট তৈরি করে -
Largest sum = 22.3333