इस समस्या में, हमें 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} समाधान दृष्टिकोण
समस्या का एक सरल समाधान सभी संभव आकार * आकार के आकार के सबअरे बनाना है, योग का पता लगाएं और फिर दिए गए योग मान के साथ इसकी बराबरी करें। अगर दोनों बराबर हों तो वापस लौटें।
एक अन्य दृष्टिकोण गतिशील प्रोग्रामिंग एल्गोरिथम . की अवधारणा का उपयोग कर रहा है . इस दृष्टिकोण में, हम एक डीपी सरणी बनाएंगे जो योग को वर्तमान सूचकांक मूल्य तक संग्रहीत करेगा यानी डीपी [i] [j] पंक्ति सूचकांक 0 से i और स्तंभ सूचकांक 0 से j तक सरणी के सभी तत्वों के योग को संग्रहीत करेगा। ।
इस डीपी सरणी का उपयोग करके, हम सूत्र का उपयोग करके किन्हीं दो प्रारंभिक अनुक्रमणिका और अंतिम अनुक्रमणिका के बीच के योग की गणना करेंगे,
$$\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 - आकार (n+1)*(n+1) का DP मैट्रिक्स बनाएं।
चरण 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!