C++ এ একটি বিন্যাসের সর্বোচ্চ গড় যোগফল

সমস্যা বিবৃতি

একটি অ্যারে দেওয়া হলে, আমরা সংখ্যার একটি সারি 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