ผลรวมสูงสุดของคู่ที่มีความต่างเฉพาะเจาะจงในโปรแกรม C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของจำนวนเต็ม n ตัวและตัวเลข d ภารกิจของเราคือสร้างโปรแกรมเพื่อหาผลรวมสูงสุดของคู่ที่มีความต่างเฉพาะเจาะจงใน C++

คำอธิบายปัญหา

เราจะหาคู่ในลักษณะที่ความต่างขององค์ประกอบของคู่น้อยกว่า d ผลรวมของคู่ทั้งหมดที่เป็นเช่นนั้นควรเป็นสูงสุด

ตัวอย่าง

อินพุต

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

เอาต์พุต

47

คำอธิบาย

คู่ที่มีส่วนทำให้ผลรวมสูงสุด: (3, 5), (7, 9), (11, 12) 
ผลรวม = 3 + 5 + 7 + 9 + 11 + 12 = 47

แนวทางแก้ปัญหา

วิธีแก้ที่ง่ายและชัดเจนคือการสร้างคู่ที่ถูกต้องทั้งหมดของอาร์เรย์แล้วหาผลรวมและคืนค่าสูงสุดของทุกผลรวม แต่วิธีนี้ไม่มีประสิทธิภาพ

วิธีแก้ที่มีประสิทธิภาพคือการใช้แนวทางการเขียนโปรแกรมแบบไดนามิก (Dynamic Programming) ที่นี่เราจะหาคู่ที่เหมาะสมที่สุดซึ่งเป็นผลรวมสูงสุด สำหรับสิ่งนี้เราจะใช้อาร์เรย์ที่เรียงลำดับแล้ว ดังนั้นเราจะเรียงอาร์เรย์ที่กำหนดให้ก่อน แล้วจึงดำเนินการกับมัน สำหรับการหาผลรวม เราจะใช้อาร์เรย์เพื่อเก็บผลรวมสูงสุดของคู่จนถึงองค์ประกอบปัจจุบัน สำหรับสิ่งนี้ เราจะตรวจสอบว่าองค์ประกอบปัจจุบันและองค์ประกอบก่อนหน้าทำเป็นคู่ได้หรือไม่ ถ้าได้ เราจะเพิ่มผลรวมของคู่เข้าไปใน maxSum จนถึงอาร์เรย์ มิฉะนั้น max sum จะคงที่

อัลกอริทึม

เริ่มต้น: DP[n]

ขั้นตอนที่ 1

สำหรับอาร์เรย์ arr[]

ขั้นตอนที่ 2

DP[0] = 0;

ขั้นตอนที่ 3

วนลูป i → 1 ถึง n

ขั้นตอนที่ 3.1

ตรวจสอบว่าคู่กับองค์ประกอบก่อนหน้าเป็นไปได้หรือไม่ if(arr[i] - arr[i-1] < d)

ขั้นตอนที่ 3.2

ถ้าได้ ตรวจสอบว่าผลรวมคู่ปัจจุบันให้ค่ามากกว่าผลรวมที่พิจารณาล่าสุดหรือไม่ และเพิ่มค่าสูงสุดเข้าไปในผลรวมปัจจุบัน
เช่น 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

ข้อยกเว้นสำหรับค่า i = 1 ซึ่งไม่มีค่า DP[i-2] เป็นไปได้ ในกรณีนี้ DP[i-2] ไม่ถูกพิจารณาเพราะเป็นผลรวมคู่แรก

ขั้นตอนที่ 4

คืนค่า 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