ผลรวมสูงสุดจากการเลือกองค์ประกอบจากสองอาร์เรย์ตามลำดับในโปรแกรม C++

ในปัญหานี้ เราได้รับสองอาร์เรย์ arr1[] และ arr2[] และสองตัวเลข N และ M

N ให้จำนวนองค์ประกอบที่หยิบจาก arr1

M ให้จำนวนองค์ประกอบที่หยิบจาก arr2

เราต้องเลือกหนึ่งในองค์ประกอบจาก arr1[i] ถึง arr2[i] ซึ่งทำให้ผลรวมสูงสุด แต่สูงสุด N ตัวจาก arr1 และ M ตัวจาก arr2

ภารกิจของเราคือสร้างโปรแกรมเพื่อหาผลรวมสูงสุดจากการเลือกองค์ประกอบจากสองอาร์เรย์ตามลำดับใน C++

ตัวอย่าง

อินพุต

arr1[] = {5, 1, 6, 2, 8, 9} 
arr2[] = {8, 4, 7, 9, 1, 3} 
M = 3, N = 2

เอาต์พุต

28

คำอธิบาย

นี่คือองค์ประกอบที่จะหยิบ:
i = 0, arr1[0] = 5, arr2[0] = 8. องค์ประกอบที่หยิบ: 8
i = 1, arr1[1] = 1, arr2[1] = 4. องค์ประกอบที่หยิบ: 4
i = 2, arr1[2] = 6, arr2[2] = 7. องค์ประกอบที่หยิบ: 6
i = 3, arr1[3] = 2, arr2[3] = 9. องค์ประกอบที่หยิบ: 2
i = 4, arr1[4] = 8, arr2[0] = 1. องค์ประกอบที่หยิบ: 8
maxSum = 8 + 4 + 6 + 2 + 8 = 28

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

ในการแก้ปัญหา วิธีแก้หนึ่งคือการหาองค์ประกอบสูงสุดของ arr1 และ arr2 จนกว่าจำนวนองค์ประกอบจะถึง M หรือ N แล้วบวกค่าทั้งหมดเพื่อหาผลรวม

อัลกอริทึม

เริ่มต้น

maxSum = 0

ขั้นตอนที่ 1

สำหรับ i → 0 ถึง n

ขั้นตอนที่ 1.1

ถ้า arr1[i] > arr2[i] และ M >= 0 → maxSum += arr1[i]

ขั้นตอนที่ 1.2

ถ้า arr1[i] < arr2[i] และ N >= 0 → maxSum += arr2[i]

ขั้นตอนที่ 1.3

อื่นๆ ออก

ขั้นตอนที่ 3

คืนค่า maxSum

ตัวอย่างโค้ด

โปรแกรมสำหรับแสดงการทำงานของวิธีแก้ปัญหาของเรา

#include <iostream> 
using namespace std; 

int calcMaxSumFromArrays(int arr1[], int arr2[], int N, int M, int size1, int size2) { 
    int maxSum = 0; 
    for(int i = 0; i < size1; i++){ 
        if(arr1[i] > arr2[i] && N > 0){ 
            maxSum += arr1[i]; 
            N--; 
        } 
        else if(arr1[i] <= arr2[i] && M > 0){ 
            maxSum += arr2[i]; 
            M--; 
        } 
        else if(M > 0){ 
            maxSum += arr2[i]; 
            M--; 
        } 
        else if(N > 0){ 
            maxSum += arr1[i]; 
            N--; 
        } 
        else 
            return maxSum; 
    } 
    return maxSum; 
} 

int main() { 
    int arr1[]= {5, 1, 6, 2, 8, 9}; 
    int arr2[]= {8, 4, 7, 9, 1, 3}; 
    int N = 3, M = 2; 
    int size1 = sizeof(arr1)/sizeof(arr1[0]); 
    int size2 = sizeof(arr2)/sizeof(arr2[0]); 
    cout << "The maximum sum by picking elements from two arrays in order is " << calcMaxSumFromArrays(arr1, arr2, N, M, size1, size2); 
    return 0; 
}

เอาต์พุต

The maximum sum by picking elements from two arrays in order is 28