এই সমস্যায়, আমাদেরকে N*N আকারের একটি 2D ম্যাট্রিক্স এবং দুটি ভেরিয়েবল যোগফল এবং আকার দেওয়া হয়েছে। আমাদের কাজ হল প্রদত্ত যোগফলের সাথে একটি সাব-ম্যাট্রিক্স খুঁজে বের করা .
আমাদের যোগফলের সমান উপাদান যোগ সহ সাইজ*সাইজের একটি সাব-ম্যাট্রিক্স খুঁজে বের করতে হবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : mat[][] = {
{1, 5, 7, 9}
{2, 4, 6, 8}
{1, 2, 5, 6}
{3, 6, 9, 3}
}
sum = 22
Size = 2
Output : YES ব্যাখ্যা −
The submatrix of size k with sum 22 is
{5, 7}
{4, 6} সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল সম্ভাব্য সকল আকার*আকারের আকারের সাব্যারে তৈরি করা, যোগফল খুঁজে বের করুন এবং তারপর প্রদত্ত যোগফলের মানের সাথে এটিকে সমান করুন। উভয়ই সমান হলে ফিরুন।
আরেকটি পদ্ধতি হল ডাইনামিক প্রোগ্রামিং অ্যালগরিদম ধারণা ব্যবহার করা . এই পদ্ধতিতে, আমরা একটি DP অ্যারে তৈরি করব যা বর্তমান সূচক মান পর্যন্ত যোগফল সংরক্ষণ করবে অর্থাৎ DP[i][j] সারি সূচক 0 থেকে i এবং কলাম সূচক 0 থেকে j পর্যন্ত অ্যারের সমস্ত উপাদানের যোগফল সংরক্ষণ করবে। .
এই DP অ্যারে ব্যবহার করে, আমরা সূত্র ব্যবহার করে যে কোনো দুটি প্রারম্ভিক সূচক এবং শেষ সূচকের মধ্যে যোগফল গণনা করব,
$$\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]}$$
অ্যালগরিদম
ধাপ 1 − আকারের একটি DP ম্যাট্রিক্স তৈরি করুন (n+1)*(n+1)।
ধাপ 2 - ম্যাট্রিক্সের প্রতিটি উপাদানের জন্য, বর্তমান সূচক পর্যন্ত যোগফল বের করুন।
ধাপ 3 − 0 থেকে n পর্যন্ত সমস্ত সূচকের জন্য, সাইজ সাইজ*সাইজের সাব-ম্যাট্রিক্সের যোগফল বের করুন। সূত্র ব্যবহার করে এবং currSum এ সংরক্ষণ করুন।
পদক্ষেপ 4৷ − যদি currSum ==যোগফল হয়, সত্য ফেরত দিন।
ধাপ 5 - মিথ্যা ফেরত দিন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#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!";
} আউটপুট
Sub-Matrix of given size having the given sum is possible!
