इस समस्या में, हमें एक सरणी arr[] और एक संख्या M दी गई है। हमारा कार्य C++ में अधिकतम वजन अंतर की गणना करने के लिए एक प्रोग्राम बनाना है।
समस्या कथन
हम सरणी से M तत्व ढूंढेंगे ताकि शेष तत्वों के योग के साथ उनके योग का निरपेक्ष अंतर अधिकतम हो।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट: arr[] = {3, 1, 6, 9, 4} M = 3
आउटपुट: 15
व्याख्या
हम 4,6,9 पर विचार करेंगे। योग 19 है। शेष संख्याओं के योग के साथ निरपेक्ष अंतर है
|19 - 4| = 15
समाधान दृष्टिकोण
समस्या का समाधान इस तथ्य पर आधारित है कि अधिकतम अंतर केवल M सबसे बड़ी संख्याओं या M सबसे छोटी संख्याओं के मामले में संभव है। और हमें दोनों शर्तों की जांच करनी होगी और अंतिम परिणाम खोजने के लिए निरपेक्ष अंतर की तुलना करनी होगी। M सबसे बड़ी/सबसे छोटी संख्याओं को खोजने की प्रक्रिया को आसान बनाने के लिए, हम सरणी को क्रमबद्ध करेंगे और फिर K सबसे बड़ी और सबसे छोटी संख्याओं पर गणना करेंगे।
उदाहरण
#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<<"अधिकतम वजन अंतर है "<<maxWeightDifference(arr,N, M); return 0; }
आउटपुट
अधिकतम वजन अंतर है 15