इस समस्या में, हमें यह निर्धारित करने के लिए C++ कोड बनाना होगा कि किसी सरणी को दो बराबर उप-सरणी में विभाजित किया जा सकता है या नहीं। साथ ही, हमें इस स्थिति की जांच करनी होगी कि क्या दोनों उपसरणियों में सभी तत्वों का योग बिल्कुल समान है या नहीं। विभाजन की समस्या सबसेट सम समस्या का एक प्रकार है, जो बदले में नैपसैक समस्या का एक प्रकार है। हम विभाजन की समस्या से निपटने के लिए C++ प्रोग्रामिंग भाषा का उपयोग करेंगे। निर्दिष्ट शर्त पूरी होती है या नहीं, इस पर निर्भर करते हुए हमें हां या नहीं के साथ एक स्ट्रिंग वापस करनी होगी।
इनपुट
arr[] = {6, 4, 8, 12, 15} आउटपुट
Is possible to divide into two subsets of equal sum
समस्या को हल करने का तरीका
लक्ष्य सेट में सभी तत्वों का योग ज्ञात करना है। जब सरणी का योग विषम होता है, तो हम इसे दो सेटों में विभाजित नहीं कर सकते। योग/2 के साथ उपसमुच्चय की पहचान करें जब योग सम हो। दिए गए सरणी का उपयोग करके, प्रत्येक तत्व की एक-एक करके जांच करें, और फिर निम्न विकल्पों में से एक चुनें:
-
वर्तमान आइटम को सबसेट में शामिल करना जारी रखें, फिर कुल तक पहुंचने के लिए बाकी को जोड़ें।
-
एक बार वर्तमान आइटम को सबसेट से हटा दिया गया है, तो अन्य वस्तुओं के लिए प्रक्रिया दोहराएं।
अंत में, यदि वर्तमान आइटम को सबसेट में शामिल या बहिष्कृत किया गया है, तो सही लौटें; अन्यथा, झूठी वापसी। यदि कोई और आइटम नहीं हैं या योग ऋणात्मक हो जाता है, तो पुनरावर्तन समाप्त हो जाता है। 0 के योग के मामले में, हम सही लौटते हैं, जिसका अर्थ है कि एक सबसेट की पहचान कर ली गई है।
उदाहरण
#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
जब कुल घटक बहुत बड़े नहीं होते हैं, तो समस्या को गतिशील प्रोग्रामिंग का उपयोग करके नियंत्रित किया जा सकता है। एक 2D सरणी भाग [] [] आकार का (योग/2 + 1)*(n+1) बनाया जा सकता है। हम नीचे से ऊपर तक समाधान भी बना सकते हैं, ताकि प्रत्येक भरी हुई प्रविष्टि में निम्नलिखित गुण हों। हम आकार के 2-डी सरणी (योग/2 + 1)*(n + 1) का उपयोग करके इस समस्या को हल कर सकते हैं। आकार का 2-डी सरणी (योग/2 + 1)*(n + 1)।
उदाहरण
#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++ प्रोग्रामिंग भाषा में पुनरावर्ती सरणियों का उपयोग करके विभाजन समस्या का समाधान किया है। यह एक मौलिक कोड है लेकिन समस्याओं को हल करने में इसके कई उपयोग हैं।