ในปัญหานี้ เราได้รับอาร์เรย์สามอาร์เรย์ arr1[], arr2[] และ arr3[] ทุกขนาด N หน้าที่ของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดจากสามอาร์เรย์ ดังนั้นการเลือกองค์ประกอบที่ต่อเนื่องกันจากที่เดียวกันไม่ใช่ อนุญาตใน C++
คำอธิบายปัญหา
เราจะหาผลรวมสูงสุดโดยเลือกองค์ประกอบ N อิลิเมนต์ i=th สามารถเลือกผลรวมจากอิลิเมนต์ที่ i ของอาร์เรย์ได้ นั่นคือ ith sum มาจาก arr1[i]/ arr2[i]/ arr3[i] นอกจากนี้ โปรดทราบว่าเราไม่สามารถเลือกสององค์ประกอบต่อเนื่องกันที่สามารถเลือกได้จากอาร์เรย์เดียวกัน
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินเอาท์
arr1[] = {5, 8, 9, 20},
arr2[] = {7, 12, 1, 10},
arr3[] = {8, 9, 10, 11}
N = 4 ผลลัพธ์
50
คำอธิบาย
สำหรับ i =1 เราจะพิจารณา 8 สำหรับผลรวมจาก arr3 สำหรับ i =2 เราจะพิจารณา 12 สำหรับผลรวมจาก arr2 สำหรับ i =3 เราจะพิจารณา 10 สำหรับผลรวมจาก arr3 สำหรับ i =4 เราจะพิจารณา 20 สำหรับผลรวมจาก arr1 ผลรวม =8 + 12 + 10 + 20 =50
แนวทางการแก้ปัญหา
ในการแก้ปัญหา เราจะใช้วิธีการเขียนโปรแกรมแบบไดนามิก เรายังต้องจำผลรวมจนถึงดัชนีเพื่อหลีกเลี่ยงการคำนวณเพิ่มเติม เราจะสร้างเมทริกซ์ 2 มิติ DP[][] องค์ประกอบที่ดัชนี i,j จะเป็นผลรวมขององค์ประกอบจนถึงดัชนีที่ i และใช้อาร์เรย์ j-th เราจะค้นหาองค์ประกอบสำหรับปัจจุบันซ้ำๆ แล้วเรียกผลรวมขององค์ประกอบถัดไปจากอีกสองอาร์เรย์
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
const int N = 3;
int findMaxVal(int a, int b){
if(a > b)
return a;
return b;
}
int FindMaximumSum(int index, int arrNo, int arr1[], int arr2[], int arr3[], int n, int DP[][N]){
if (index == n)
return 0;
if (DP[index][arrNo] != -1)
return DP[index][arrNo];
int maxVal = -1;
if (arrNo == 0){
maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));
maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));
}
else if (arrNo == 1){
maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));
maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));
}
else if (arrNo == 2){
maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));
maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));
}
return DP[index][arrNo] = maxVal;
}
int main(){
int arr1[] = { 5, 8, 9, 20 };
int arr2[] = { 7, 12, 1, 10 };
int arr3[] = { 8, 9, 10, 11 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int DP[n][N];
memset(DP, -1, sizeof DP);
int val1 = FindMaximumSum(0, 0, arr1, arr2, arr3, n, DP);
int val2 = FindMaximumSum(0, 1, arr1, arr2, arr3, n, DP);
int val3 = FindMaximumSum(0, 2, arr1, arr2, arr3, n, DP);
cout<<"The maximum sum from three arrays such that picking elements consecutively from same is not allowed is "<<findMaxVal(val1, findMaxVal(val2, val3));
return 0;
} ผลลัพธ์
The maximum sum from three arrays such that picking elements consecutively from same is not allowed is 50
