คำอธิบายปัญหา
ในปัญหานี้ เราได้รับอาร์เรย์สามอาร์เรย์ arr1[], arr2[], และ arr3[] ทั้งหมดมีขนาด N งานของเราคือการเขียนโปรแกรมเพื่อหาผลรวมสูงสุดจากอาร์เรย์สามอาร์เรย์ โดยที่ห้ามเลือกองค์ประกอบติดกันจากอาร์เรย์เดียวกัน
เราจะหาผลรวมสูงสุดโดยการเลือก N องค์ประกอบ องค์ประกอบที่ i สามารถเลือกได้จาก 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
แนวทางแก้ปัญหา
ในการแก้ปัญหานี้ เราจะใช้แนวทางการเขียนโปรแกรมแบบไดนามิก (Dynamic Programming) พร้อมกับการจดจำผลรวมจนถึงดัชนีปัจจุบันเพื่อหลีกเลี่ยงการคำนวณซ้ำ เราจะสร้างเมทริกซ์ 2 มิติ DP[][] โดยที่องค์ประกอบที่ดัชนี i,j จะเป็นผลรวมขององค์ประกอบจนถึงดัชนี i โดยใช้อาร์เรย์ที่ j เราจะหาค่าสำหรับดัชนีปัจจุบันแบบเรียกซ้ำ (recursive) แล้วเรียกหาผลรวมขององค์ประกอบถัดไปจากอีกสองอาร์เรย์
ตัวอย่างโค้ด
โปรแกรมตัวอย่างสำหรับการทำงานของวิธีแก้ปัญหา:
#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
