Trong bài toán này, chúng ta được cung cấp một lưới hình chữ nhật có kích thước 2 x n. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm Tổng lớn nhất trong lưới 2 x n sao cho không có hai phần tử nào liền kề trong C ++.
Mô tả vấn đề
Để tìm tổng lớn nhất, chúng tôi không thể chọn các phần tử liền kề với phần tử hiện tại, theo chiều dọc, chiều ngang hoặc đường chéo.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
rectGrid[2][] =389 411
Đầu ra
13
Giải thích
tất cả các khoản tiền có thể có là
Nếu chúng ta bắt đầu từ directGrid [0] [0] tức là 3, thì chúng ta chỉ có thể thêm 9 hoặc 1. Giá trị tối đa là 12.
Nếu chúng ta bắt đầu từ directGrid [1] [0] tức là 4, thì chúng ta chỉ có thể thêm 9 hoặc 1. Giá trị maxSum là 13.
Nếu chúng ta bắt đầu từ directGrid [0] [1] tức là 8, thì chúng ta không thể thêm bất kỳ phần tử nào. Giá trị tối đa là 8.
Nếu chúng ta bắt đầu từ directGrid [1] [1] tức là 1, thì chúng ta không thể thêm bất kỳ phần tử nào. Giá trị tối đa là 1.
Nếu chúng ta bắt đầu từ directGrid [0] [2] tức là 9, thì chúng ta chỉ có thể thêm 3 hoặc 4. Giá trị tối đa là 13.
Nếu chúng ta bắt đầu từ directGrid [1] [2] tức là 1, thì chúng ta chỉ có thể thêm 3 hoặc 4. Giá trị tối đa là 5.
Tổng tối đa tổng thể là 13.
Phương pháp tiếp cận giải pháp
Bài toán tương tự với tổng tối đa sao cho không có hai phần tử nào liền kề mà chúng ta đã thấy trong bài trước. Sự khác biệt là mảng ở đây là 2D và điều kiện cho các phần tử liền kề. Vì vậy, chúng tôi sẽ xem xét phần tử tối đa sử dụng điều kiện cho cả hàng và cột. Vì mỗi cột có hai hàng, chúng tôi sẽ xem xét tối đa các yếu tố thay thế có thể có.
Ví dụ
Chương trình minh họa hoạt động của giải pháp,
#include<iostream>
using namespace std;
int findMax(int a, int b){
if(a > b)
return a;
return b;
}
int calcMaxSum(int rectGrid[2][20], int N){
int currectSum = 0;
int nextSum = 0;
int altSum;
for (int i = 0; i<N; i++ ){
altSum = findMax(nextSum, currectSum);
currectSum = nextSum + findMax(rectGrid[0][i], rectGrid[1][i]);
nextSum = altSum;
}
int maxSum = findMax(nextSum, currectSum);
return maxSum;
}
int main(){
int rectGrid[2][20] = {{3, 8, 9, 5},
{4, 1, 2, 7}};
int N = 4;
cout<<"The maximum sum in a 2 x "<<N<<" grid such that no two elements are adjacent is "<<calcMaxSum(rectGrid, N);
return 0;
} Đầu ra
The maximum sum in a 2 x 4 grid such that no two elements are adjacent is 15