คำชี้แจงปัญหา
จากอาร์เรย์ เราแบ่งแถวของตัวเลข 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
