Tuyên bố vấn đề
Cho một mảng, chúng ta phân chia một hàng số A thành nhiều nhất K nhóm liền kề (không trống), khi đó điểm là tổng trung bình của mỗi nhóm. Điểm tối đa có thể ghi được là bao nhiêu?
Ví dụ
Nếu mảng đầu vào là {9, 2, 5, 3, 10} thì chúng ta có thể phân vùng mảng như sau -
{9} {2, 5, 3} và {10} thì tổng trung bình của giá trị này là -
9 + (2 + 5 + 3) / 3 + 10 =22,33
Thuật toán
Chúng ta có thể sử dụng kỹ thuật ghi nhớ để giải quyết vấn đề này -
- Để ghi nhớ [i] [k] là điểm tốt nhất khi chia phần A [i đến n-1] thành nhiều nhất K phần
- Trong nhóm đầu tiên, chúng tôi phân vùng A [i đến n-1] thành A [i đến j-1] và A [j đến n-1], sau đó phân vùng ứng cử viên của chúng tôi có điểm trung bình (i, j) + điểm (j, k-1)), trong đó trung bình (i, j) =(A [i] + A [i + 1] +… + A [j-1]) / (j - i). Chúng tôi lấy điểm cao nhất trong số này
- Tổng cộng, đệ quy của chúng ta trong trường hợp chung là:memo [n] [k] =max (memo [n] [k], điểm (memo, i, A, k-1) + trung bình (i, j ))
Ví dụ
Bây giờ chúng ta hãy xem một ví dụ -
#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;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Largest sum = 22.3333