विभाजन की समस्या

इस समस्या के लिए, किसी दिए गए समुच्चय को इस प्रकार विभाजित किया जा सकता है, कि प्रत्येक उपसमुच्चय का योग बराबर हो।

सबसे पहले हमें दिए गए समुच्चय का योग ज्ञात करना है। यदि यह सम है, तो इसे दो सेटों में विभाजित करने का मौका है। अन्यथा, इसे विभाजित नहीं किया जा सकता।

योग के सम मान के लिए, हम partTable नाम की एक तालिका बनाएंगे, अब समस्या को हल करने के लिए निम्न शर्त का उपयोग करें।

partTable[i, j] सत्य है, जब array[0] से array[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.