C++에서 배열의 최대 평균 합계 파티션

문제 설명

주어진 배열에서 숫자 A의 행을 최대 K개의 인접한(비어 있지 않은) 그룹으로 분할한 다음 점수는 각 그룹의 평균 합계입니다. 채점할 수 있는 최대 점수는 얼마입니까?

예

입력 배열이 {9, 2, 5, 3, 10}이면 다음과 같이 배열을 분할할 수 있습니다. -

{9} {2, 5, 3} 및 {10}의 평균 합계는 -

9 + (2 + 5 + 3)/ 3 + 10 =22.33

알고리즘

우리는 이 문제를 해결하기 위해 암기 기술을 사용할 수 있습니다 -

• 메모[i][k]를 A[i에서 n-1]까지의 최대 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] =max(memo[n][k], score(memo, i, A, k-1) + average(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