পার্টিশন সমস্যা

এই সমস্যার জন্য, একটি প্রদত্ত সেটকে এমনভাবে বিভাজন করা যেতে পারে, যাতে প্রতিটি উপসেটের যোগফল সমান হয়৷

প্রথমে, আমাদের প্রদত্ত সেটের যোগফল বের করতে হবে। যদি এটি সমান হয়, তাহলে এটিকে দুটি সেটে ভাগ করার সুযোগ রয়েছে। অন্যথায়, এটি ভাগ করা যাবে না।

যোগফলের জোড় মানের জন্য, তারপর আমরা partTable নামে একটি টেবিল তৈরি করব, এখন সমস্যাটি সমাধান করতে নিম্নলিখিত শর্তটি ব্যবহার করুন।

partTable[i, j] সত্য, যখন অ্যারে[0] থেকে অ্যারে[j-1]-এর সাবসেটের যোগফল i-এর সমান হয়, অন্যথায় এটি মিথ্যা।

ইনপুট এবং আউটপুট

Input:
A set of integers. {3, 1, 1, 2, 2, 1}
Output:
True if the set can be partitioned into two parts with equal sum.
Here the answer is true. One pair of the partitions are: {3, 1, 1}, {2, 2, 1}

অ্যালগরিদম

checkPartition(set, n)

ইনপুট - প্রদত্ত সেট, সেটের উপাদানের সংখ্যা।

আউটপুট - বিভাজন করার সময় সমান যোগফলের দুটি উপসেট তৈরি করা সম্ভব হলে সত্য।

Begin
   sum := sum of all elements in the set
   if sum is odd, then
      return

   define partTable of order (sum/2 + 1 x n+1)
   set all elements in the 0th row to true
   set all elements in the 0th column to false

   for i in range 1 to sum/2, do
      for j in range 1 to n, do
         partTab[i, j] := partTab[i, j-1]
         if i >= set[j-1], then
            partTab[i, j] := partTab[i, j] or with
            partTab[i – set[j-1], j-1]
      done
   done

   return partTab[sum/2, n]
End

উদাহরণ

#include <iostream>
using namespace std;

bool checkPartition (int set[], int n) {
   int sum = 0;

   for (int i = 0; i < n; i++)    //find the sum of all elements of set
      sum += set[i];

   if (sum%2 != 0)     //when sum is odd, it is not divisible into two set
      return false;

   bool partTab[sum/2+1][n+1];    //create partition table
   for (int i = 0; i <= n; i++)
      partTab[0][i] = true;    //for set of zero element, all values are true

   for (int i = 1; i <= sum/2; i++)
      partTab[i][0] = false;    //as first column holds empty set, it is false

   // Fill the partition table in botton up manner
   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.