এই সমস্যায় একটি প্রদত্ত সেটকে এমনভাবে পার্টিশান করা হয় যাতে প্রতিটি সাবসেটের যোগফল সমান হয়।
প্রথমে প্রদত্ত সেটের যোগফল বের করতে হয়। যদি সেটি জোড় হয়, তবে এটি দুটি সেটে ভাগ করার সম্ভাবনা থাকে। অন্যথায় ভাগ করা সম্ভব নয়।
যোগফল জোড় হলে, partTable নামক একটি টেবিল তৈরি করা হয় এবং নিচের শর্ত ব্যবহার করে সমস্যা সমাধান করা হয়।
partTable[i, j] সত্য হবে যখন array[0] থেকে array[j-1]-এর সাবসেটের যোগফল i-এর সমান হবে, অন্যথায় মিথ্যা।
ইনপুট এবং আউটপুট
ইনপুট: পূর্ণসংখ্যাগুলোর একটি সেট।
{3, 1, 1, 2, 2, 1}
আউটপুট: সেটকে সমান যোগফলवाले দুটি অংশে ভাগ করা সম্ভব কিনা। এখানে উত্তর true।
একটি পার্টিশান জোড়া: {3, 1, 1}, {2, 2, 1}
অ্যালগরিদম
checkPartition(set, n)
ইনপুট: প্রদত্ত সেট, সেটে উপাদান সংখ্যা।
আউটপুট: সমান যোগফলवाले দুটি সাবসেটে পার্টিশান সম্ভব হলে true।
শুরু
sum := সেটের সকল উপাদানের যোগফল
যদি sum বিজোড় হয়, তবে
ফেরত দিন false
(sum/2 + 1) x (n+1) ক্রমের partTable সংজ্ঞায়িত করুন
০-তম সারির সকল উপাদান true সেট করুন
০-তম কলামের সকল উপাদান false সেট করুন
i := 1 থেকে sum/2 পর্যন্ত রেঞ্জে, করুন
j := 1 থেকে n পর্যন্ত রেঞ্জে, করুন
partTab[i, j] := partTab[i, j-1]
যদি i >= set[j-1] হয়, তবে
partTab[i, j] := partTab[i, j] OR partTab[i - set[j-1], j-1]
শেষ
শেষ
partTab[sum/2, n] ফেরত দিন
শেষ
উদাহরণ (C++)
#include <iostream>
using namespace std;
bool checkPartition(int set[], int n) {
int sum = 0;
for (int i = 0; i < n; i++)
sum += set[i];
if (sum % 2 != 0)
return false;
bool partTab[sum/2+1][n+1];
for (int i = 0; i <= n; i++)
partTab[0][i] = true;
for (int i = 1; i <= sum/2; i++)
partTab[i][0] = false;
for (int i = 1; i <= sum/2; i++) {
for (int j = 1; j <= n; j++) {
partTab[i][j] = partTab[i][j-1];
if (i >= set[j-1])
partTab[i][j] = partTab[i][j] || partTab[i - set[j-1]][j-1];
}
}
return partTab[sum/2][n];
}
int main() {
int set[] = {3, 1, 1, 2, 2, 1};
int n = 6;
if (checkPartition(set, n))
cout << "Given Set can be divided into two subsets of equal sum.";
else
cout << "Given Set can not be divided into two subsets of equal sum.";
}
আউটপুট
Given Set can be divided into two subsets of equal sum.
