এই সমস্যায়, একটি অ্যারেকে দুটি সমান সাবয়ারেতে ভাগ করা যেতে পারে কিনা তা নির্ধারণ করতে আমাদের অবশ্যই 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 অ্যারে অংশ[][][] আকারের (sum/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++ প্রোগ্রামিং ভাষায় রিকার্সিভ অ্যারে ব্যবহার করে পার্টিশন সমস্যার সমাধান করেছি। এটি একটি মৌলিক কোড কিন্তু সমস্যা সমাধানে এর অনেক ব্যবহার রয়েছে।
