इस समस्या में, हमें एक सरणी arr[] और एक संख्या M दी जाती है। हमारा कार्य C++ में अधिकतम भार अंतर की गणना करने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण
We will find M elements from the array such that the absolute difference between the sum and the sum of the rest elements is maximum.
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {3, 1, 6, 9, 4} M = 3 आउटपुट
15
स्पष्टीकरण
हम 4,6,9 पर विचार करेंगे। योग 19 है। शेष संख्याओं के योग के साथ पूर्ण अंतर है
|19 − 4| = 15
समाधान दृष्टिकोण
समस्या का एक सरल समाधान है, सरणी के सभी अनुक्रमों को खोजना, उप-सरणी के योग तत्वों को खोजना, और शेष। और अधिकतम अंतर लौटाएं।
एक अधिक कुशल समाधान इस तथ्य का उपयोग करके पाया जाता है कि अधिकतम भार अंतर यानी तत्वों के योग का अंतर और शेष अधिकतम होता है यदि हम बाद के लिए एम अधिकतम तत्वों या एम न्यूनतम तत्वों पर विचार करते हैं।
इसलिए, हम सबसे बड़े तत्वों और बाकी सरणी या एम सबसे छोटे तत्वों और बाकी सरणी के बाद के लिए अधिकतम योग अंतर की जांच करेंगे।
और दोनों का अधिकतम लौटाएं।
एल्गोरिदम
आरंभ करें -
maxSum , maxSumDiff, minSumDiff
चरण 1 -
sort the array in descending order.
चरण 2 -
Loop for i −> 0 to n
चरण 2.1 -
if (i < m) −> maxSumDiff += arr[i]
चरण 2.2 -
else −> maxSumDiff −= arr[i]
चरण 2 -
Loop for i −> n to 0
चरण 2.1 -
if (i > m) −> minSumDiff += arr[i]
चरण 2.2 -
else −> minSumDiff −= arr[i]
चरण 3 -
if maxSumDiff > minSumDiff −> maxSum = maxSumDiff.
चरण 4 -
if maxSumDiff < minSumDiff −> maxSum = minSumDiff.
चरण 5 -
return maxSum.
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include <bits/stdc++.h>
using namespace std;
int maxWeightDifference(int arr[], int N, int M){
int maxabsDiff = −1000;
sort(arr, arr + N);
int sumMin = 0, sumMax = 0, arrSum = 0;
for(int i = 0; i < N; i++){
arrSum += arr[i];
if(i < M)
sumMin += arr[i];
if(i >= (N−M))
sumMax += arr[i];
}
maxabsDiff = max(abs(sumMax − (arrSum − sumMax)), abs(sumMin −
(arrSum − sumMin)));
return maxabsDiff;
}
int main(){
int arr[] = {3, 1, 6, 9, 4} ;
int M = 3;
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum weight difference is "<<maxWeightDifference(arr,N, M);
return 0;
} आउटपुट
The maximum weight difference is 15. है