Tìm ma trận con với tổng cho trước trong C ++

Trong bài toán này, chúng ta được cung cấp một ma trận 2D có kích thước N * N và hai biến tổng và kích thước. Nhiệm vụ của chúng ta là tìm một ma trận con với tổng đã cho .

Chúng ta cần tìm một ma trận con có kích thước * size với tổng phần tử bằng tổng.

Hãy lấy một ví dụ để hiểu vấn đề,

Input : mat[][] = {
   {1, 5, 7, 9}
   {2, 4, 6, 8}
   {1, 2, 5, 6}
   {3, 6, 9, 3}
}
sum = 22
Size = 2
Output : YES

Giải thích -

The submatrix of size k with sum 22 is
{5, 7}
{4, 6}

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là tạo tất cả các phân thức con có kích thước size * size có thể có, tìm tổng và sau đó cân bằng nó với giá trị tổng đã cho. Trả lại nếu cả hai đều bằng nhau.

Một cách tiếp cận khác là sử dụng khái niệm Thuật toán lập trình động . Trong cách tiếp cận này, chúng tôi sẽ tạo một mảng DP sẽ lưu trữ tổng cho đến giá trị chỉ mục hiện tại, tức là DP [i] [j] sẽ lưu trữ tổng của tất cả các phần tử của mảng từ chỉ số hàng 0 đến i và chỉ số cột 0 đến j .

Sử dụng mảng DP này, chúng tôi sẽ tính tổng giữa hai chỉ số bắt đầu và chỉ số kết thúc bất kỳ bằng cách sử dụng công thức,

$$ \ mathrm {sum ((i_s, j_s) to (i_e, j_e)) \:=\:DP [i_s] [i_s] \:+ \:DP [i_e] [i_e] \:- \:DP [ i_s] [i_e] \:- \:DP [i_e] [i_s]} $$

Thuật toán

Bước 1 - Tạo ma trận DP có kích thước (n + 1) * (n + 1).

Bước 2 - Đối với mỗi phần tử của ma trận, hãy tìm tổng cho đến chỉ số hiện tại.

Bước 3 - Với tất cả các chỉ số từ 0 đến n, tìm tổng của ma trận con có kích thước size * size. Sử dụng công thức và lưu trữ trong currSum.

Bước 4 - if currSum ==sum, trả về true.

Bước 5 - trả về false.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#include <iostream>
using namespace std;
#define N 4
bool findSubMatWithSum(int size, int sum, int mat[N][N]){
   int DP[N + 1][N + 1];
   for (int i = 0; i < N; i++)
   for (int j = 0; j < N; j++)
   DP[i + 1][j + 1] = DP[i + 1][j] + DP[i][j + 1] - DP[i][j] + mat[i][j];
   int currSum = 0;
   for (int i = 0; i < N; i++)
   for (int j = 0; j < N; j++) {
      currSum = DP[i][j] + DP[(i + size)][(j + size)] - DP[(i + size)][j] - DP[i][(j + size)];
      if (currSum == sum)
      return true;
   }
   return false;
}
int main(){
   int mat[N][N] = { { 1, 5, 7, 9 },
   { 2, 4, 6, 8 },
   { 1, 2, 5, 6 },
   { 3, 6, 9, 3 } };
   int size = 2;
   int sum = 22;
   if (findSubMatWithSum(size, sum, mat))
      cout<<"Sub-Matrix of given size having the given sum is possible!";
   else
     cout<<"Sub-Matrix of given size having the given sum is not possible!";
}

Đầu ra

Sub-Matrix of given size having the given sum is possible!