Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm n số nguyên và một số d. Nhiệm vụ của chúng ta là tạo một chương trình để tìm tổng lớn nhất của các cặp có sự khác biệt cụ thể trong c ++ .
Mô tả sự cố - Ta sẽ tìm các cặp sao cho hiệu số phần tử của các cặp nhỏ hơn d. Tổng của tất cả các cặp như vậy phải là tối đa.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {5, 9, 11, 7, 2, 12, 3} d = 5 Đầu ra
47
Giải thích
Pairs that contribute to maximum sum: (3, 5), (7, 9), (11, 12). Sum = 3 + 5 + 7 + 9 + 11 + 12 = 47
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản và rõ ràng cho vấn đề là tạo tất cả các cặp hợp lệ của mảng, sau đó tìm tổng và trả về giá trị lớn nhất của tất cả các tổng. Nhưng giải pháp này không hiệu quả.
Một giải pháp hiệu quả cho vấn đề là sử dụng một ứng dụng lập trình động. Ở đây, chúng tôi sẽ tìm các cặp tối ưu tạo thành giá trị tối đa. Đối với điều này, chúng ta sẽ sử dụng một mảng được sắp xếp, vì vậy trước tiên chúng ta sẽ sắp xếp mảng givenar và sau đó thao tác trên nó. Để tìm tổng, chúng ta sẽ sử dụng một mảng để lưu trữ tổng lớn nhất của các cặp cho đến phần tử hiện tại. Đối với điều này, chúng tôi sẽ kiểm tra xem các phần tử hiện tại và các phần tử trước đó có tạo thành một cặp hay không. Nếu có, chúng tôi sẽ thêm tổng cặp vào maxSum cho đến khi mảng. Nếu không, giá trị tối đa sẽ vẫn như cũ.
Thuật toán
Initialize: DP[n]
Bước 1 -
For array arr[].
Bước 2
DP[0] = 0;
Bước 3 -
loop for i −> 1 to n
Bước 3.1 -
check if pairs with the previous element is possible. if(arr[i] − arr[i−1] < d).
Bước 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].
Bước 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.
Bước 4 -
Return DP[n−1].
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
The maximum sum of pairs with specific difference is 47