इस समस्या में, हमें N*N आकार का एक 2D मैट्रिक्स और दो वेरिएबल योग और आकार दिए गए हैं। हमारा कार्य दिए गए योग वाला एक सब-मैट्रिक्स ढूंढना है।
हमें आकार*आकार का एक सब-मैट्रिक्स ढूंढना है जिसके तत्वों का योग दिए गए योग के बराबर हो।
उदाहरण से समझते हैं:
इनपुट: mat[][] = { {1, 5, 7, 9} {2, 4, 6, 8} {1, 2, 5, 6} {3, 6, 9, 3} } योग = 22 आकार = 2 आउटपुट: YES व्याख्या:
आकार k का योग 22 वाला सबमैट्रिक्स है {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 - (n+1)*(n+1) आकार का एक DP मैट्रिक्स बनाएं।
चरण 2 - मैट्रिक्स के प्रत्येक तत्व के लिए, वर्तमान इंडेक्स तक का योग ज्ञात करें।
चरण 3 - 0 से n तक सभी इंडेक्स के लिए, आकार*आकार के सब-मैट्रिक्स का योग सूत्र का उपयोग करके ज्ञात करें और currSum में संग्रहीत करें।
चरण 4 - यदि currSum == योग, तो true लौटाएं।
चरण 5 - false लौटाएं।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
#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!
