Tìm tổng lớn nhất của các cặp với hiệu số cụ thể trong C++

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ụ là viết chương trình tìm tổng lớn nhất của các cặp với hiệu số cụ thể trong C++.

Mô tả bài toán

Chúng ta sẽ tìm các cặp sao cho hiệu của hai phần tử trong cặp nhỏ hơn d. Tổng của tất cả các cặp như vậy phải lớn nhất.

Ví dụ minh họa

Đầu vào

arr[] = {5, 9, 11, 7, 2, 12, 3}
d = 5

Đầu ra

47

Giải thích

Các cặp góp phần vào tổng lớn nhất: (3, 5), (7, 9), (11, 12).
Tổng = 3 + 5 + 7 + 9 + 11 + 12 = 47

Phương pháp giải

Cách đơn giản là tạo tất cả các cặp hợp lệ từ mảng, tìm tổng và trả về tổng lớn nhất. Nhưng cách này không hiệu quả.

Cách hiệu quả sử dụng quy hoạch động. Ta tìm các cặp tối ưu tạo thành tổng lớn nhất. Đầu tiên sắp xếp mảng, sau đó xử lý trên mảng đã sắp xếp. 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. Kiểm tra xem phần tử hiện tại và phần tử trước đó có tạo thành cặp hợp lệ không. Nếu có, cộng tổng cặp vào maxSum cho đến vị trí đó. Ngược lại, max sum giữ nguyên.

Thuật toán

Khởi tạo: DP[n]

Bước 1

Đối với mảng arr[].

Bước 2

DP[0] = 0;

Bước 3

Vòng lặp i từ 1 đến n-1

Bước 3.1

Kiểm tra xem cặp với phần tử trước có hợp lệ không: if(arr[i] - arr[i-1] < d).

Bước 3.2

Nếu có, kiểm tra xem tổng cặp hiện tại có lớn hơn tổng đã xét trước không và thêm giá trị lớn nhất vào tổng hiện tại.
Tức là 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

Ngoại lệ cho i = 1, không có giá trị DP[i-2], trong trường hợp này DP[i-2] không được xét vì đây là tổng cặp đầu tiên.

Bước 4

Trả về DP[n-1].

Chương trình minh họa

#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 << "Tổng lớn nhất của các cặp với hiệu số cụ thể là " << CalcmaxPairSum(arr, n, d);
    return 0;
}

Đầu ra

Tổng lớn nhất của các cặp với hiệu số cụ thể là 47