इस समस्या में, हमें n पूर्णांकों की एक सरणी arr[] और एक संख्या d दी जाती है। हमारा कार्य c++ में विशिष्ट अंतर वाले युग्मों की अधिकतम राशि ज्ञात करने के लिए एक प्रोग्राम बनाना है। ।
समस्या का विवरण - हम युग्मों को इस प्रकार पाएंगे कि युग्मों के तत्वों का अंतर d से कम हो। ऐसे सभी जोड़ियों का योग अधिकतम होना चाहिए।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {5, 9, 11, 7, 2, 12, 3} d = 5 आउटपुट
47
स्पष्टीकरण
Pairs that contribute to maximum sum: (3, 5), (7, 9), (11, 12). Sum = 3 + 5 + 7 + 9 + 11 + 12 = 47
समाधान दृष्टिकोण
समस्या का एक सरल और स्पष्ट समाधान सरणियों के सभी मान्य जोड़े बनाकर है और फिर योग का पता लगाएं और सभी राशियों का अधिकतम वापस करें। Butthis समाधान कारगर नहीं है।
एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करके समस्या का एक कुशल समाधान है। यहां, हमें ऐसे इष्टतम जोड़े मिलेंगे जो अधिकतम योग बनाते हैं। इसके लिए हम एक क्रमबद्ध सरणी का उपयोग करेंगे, इसलिए पहले हम दिए गए सरणी को क्रमबद्ध करेंगे और फिर उस पर काम करेंगे। योग खोजने के लिए, हम वर्तमान तत्व तक जोड़े के अधिकतम योग को संग्रहीत करने के लिए एक सरणी का उपयोग करेंगे। इसके लिए, हम जांच करेंगे कि क्या वर्तमान तत्व और पिछले तत्व एक जोड़ी बनाते हैं। यदि हाँ, तो हम जोड़ी योग को सरणी तक maxSum में जोड़ देंगे। अन्यथा, अधिकतम राशि जस की तस बनी रहेगी।
एल्गोरिदम
Initialize: DP[n]
चरण 1 -
For array arr[].
चरण 2
DP[0] = 0;
चरण 3 -
loop for i −> 1 to n
चरण 3.1 -
check if pairs with the previous element is possible. if(arr[i] − arr[i−1] < d).
चरण 3.2 -
if Yes, check if the current pair sum results in a greater value than the last considered sum and add the maximum value to the current sum. i.e. if( (DP[i−2] + arr[i−1] + arr[i]) > (DP[i−1])) −> DP[i] = (DP[i−2] + arr[i−1] + arr[i]), else −> DP[i] = DP[i−1].
चरण 3.3 -
an exception is for value i = 1, where no value of DP[i−2] is possible, in this case, DP[i−2] is not considered as it is the first pair sum.
चरण 4 -
Return DP[n−1].
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include <bits/stdc++.h>
using namespace std;
int CalcmaxPairSum(int arr[], int n, int d) {
sort(arr, arr+n);
int maxSumDP[n];
maxSumDP[0] = 0;
for (int i = 1; i < n; i++) {
maxSumDP[i] = maxSumDP[i−1];
if (arr[i] − arr[i−1] < d) {
if (i >= 2)
if(maxSumDP[i] < (maxSumDP[i−2] + arr[i−1] +
arr[i]))
maxSumDP[i] = (maxSumDP[i−2] + arr[i−1] +
arr[i]);
else
if(maxSumDP[i] < (arr[i−1] + arr[i]))
maxSumDP[i] = arr[i−1] + arr[i];
}
}
return maxSumDP[n−1];
}
int main() {
int arr[] = {5, 9, 11, 7, 2, 12, 3};
int n = 7, d = 5;
cout<<"The maximum sum of pairs with specific difference is "<<CalcmaxPairSum(arr, n, d);
return 0;
} आउटपुट
The maximum sum of pairs with specific difference is 47