समस्या कथन
एक सरणी को देखते हुए, हम संख्या 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) + स्कोर (जे, के -1)), जहां औसत (आई, जे) =(ए [i] + ए [i + 1] + … + ए [जे -1]) / (जे - आई)। हम इनमें से उच्चतम स्कोर लेते हैं
- कुल मिलाकर, सामान्य स्थिति में हमारा रिकर्सन है:मेमो [एन] [के] =अधिकतम (मेमो [एन] [के], स्कोर (मेमो, आई, ए, के -1) + औसत (आई, जे ))
उदाहरण
आइए अब एक उदाहरण देखें -
#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