इस समस्या में, हमें C++ कोड बनाना होगा यह निर्धारित करने के लिए कि क्या एक सरणी को दो समान उपसरणियों में विभाजित किया जा सकता है। साथ ही, हमें यह जांचना होगा कि क्या दोनों उपसरणियों में सभी तत्वों का योग बिल्कुल समान है या नहीं। पार्टीशन समस्या सबसेट सम समस्या का एक प्रकार है, जो बदले में नैपसैक समस्या का एक प्रकार है। हम C++ प्रोग्रामिंग भाषा का उपयोग करके पार्टीशन समस्या से निपटेंगे। हमें एक स्ट्रिंग वापस करनी होगी जिसमें Yes या No हो, यह इस पर निर्भर करता है कि निर्दिष्ट शर्त पूरी होती है या नहीं।
इनपुट
arr[] = {6, 4, 8, 12, 15}
आउटपुट
Is possible to divide into two subsets of equal sum
समस्या हल करने का दृष्टिकोण
लक्ष्य सेट में सभी तत्वों का योग ढूंढना है। जब सरणी का कुल योग विषम होता है, तो हम इसे दो सेट में विभाजित नहीं कर सकते। जब कुल योग सम हो तो योग/2 वाले सबसेट की पहचान करें। दी गई सरणी का उपयोग करके, प्रत्येक तत्व को एक-एक करके देखें, और फिर निम्नलिखित विकल्पों में से एक चुनें:
वर्तमान आइटम को सबसेट में शामिल करना जारी रखें, फिर कुल तक पहुंचने के लिए बाकी को जोड़ें।
एक बार वर्तमान आइटम को सबसेट से हटा दिए जाने के बाद, अन्य आइटम के लिए प्रक्रिया दोहराएं।
अंत में, यदि वर्तमान आइटम किसी सबसेट में शामिल या बाहर है तो true वापस करें; अन्यथा, false वापस करें। पुनरावृत्ति समाप्त होती है, यदि कोई और आइटम नहीं हैं या यदि योग नकारात्मक हो जाता है। योग 0 के मामले में, हम true वापस करते हैं, जिसका अर्थ है कि एक सबसेट पहचाना गया है।
उदाहरण
#include <bits/stdc++.h> using namespace std; bool isSubsetSum(int arr[], int n, int sum) { if (sum == 0) return true; if (n == 0 && sum != 0) return false; if (arr[n - 1] > sum) return isSubsetSum(arr, n - 1, sum); return isSubsetSum(arr, n - 1, sum) || isSubsetSum(arr, n - 1, sum - arr[n - 1]); } bool findPartiion(int arr[], int n) { int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; if (sum % 2 != 0) return false; return isSubsetSum(arr, n, sum / 2); } int main() { int arr[] = { 6, 4, 8, 12, 15 }; int n = sizeof(arr) / sizeof(arr[0]); if (findPartiion(arr, n) == true) cout << "Is possible to divide into two subsets " "of equal sum"; else cout << "Is impossible to divide into two subsets" " of equal sum"; return 0; }
आउटपुट
Is impossible to divide into two subsets of equal sum
दृष्टिकोण 2
जब घटकों का कुल बहुत बड़ा नहीं होता है, तो समस्या को डायनामिक प्रोग्रामिंग का उपयोग करके हल किया जा सकता है। आकार (sum/2 + 1)*(n+1) का एक 2D सरणी part[][] बनाया जा सकता है। हम समाधान को नीचे से ऊपर भी बना सकते हैं, ताकि प्रत्येक भरी हुई प्रविष्टि में निम्नलिखित गुण हो। हम इस मुद्दे को आकार (sum/2 + 1)*(n + 1) के 2-D सरणी का उपयोग करके हल कर सकते हैं बजाय आकार (sum/2 + 1)*(n + 1) के 2-D सरणी के।
उदाहरण
#include <bits/stdc++.h> using namespace std; bool findPartiion(int arr[], int n) { int sum = 0; int i, j; for (i = 0; i < n; i++) sum += arr[i]; if (sum % 2 != 0) return false; bool part[sum / 2 + 1]; for (i = 0; i <= sum / 2; i++) { part[i] = 0; } for (i = 0; i < n; i++) { for (j = sum / 2; j >= arr[i]; j--){ if (part[j - arr[i]] == 1 || j == arr[i]) part[j] = 1; } } return part[sum / 2]; } int main() { int arr[] = { 6, 4, 8, 12, 15 }; int n = sizeof(arr) / sizeof(arr[0]); if (findPartiion(arr, n) == true) cout << "Is possible to divide into two subsets of equal " "sum"; else cout << "Is impossible to divide into two subsets" " of equal sum"; return 0; }
आउटपुट
Is impossible to divide into two subsets of equal sum
निष्कर्ष
इस समस्या में, हमने C++ कोड के साथ पार्टीशन समस्याओं को हल करना सीखा। यह कोड जावा, पायथन और अन्य भाषाओं में भी लिखा जा सकता है। हमने C++ प्रोग्रामिंग भाषा में पुनरावर्ती सरणियों का उपयोग करके पार्टीशन समस्या को हल किया है। यह एक मौलिक कोड है लेकिन समस्याओं को हल करने में इसके कई उपयोग हैं।
