पार्टीशन समस्या

इस समस्या के लिए, एक दिए गए सेट को इस तरह पार्टीशन किया जा सकता है कि प्रत्येक सबसेट का योग बराबर हो।

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

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

partTable[i, j] तब सत्य होता है जब array[0] से array[j-1] तक के सबसेट का योग i के बराबर हो, अन्यथा यह असत्य होता है।

इनपुट और आउटपुट

इनपुट: पूर्णांकों का एक सेट
{3, 1, 1, 2, 2, 1}

आउटपुट: सत्य यदि सेट को समान योग के दो भागों में विभाजित किया जा सकता है। यहां उत्तर सत्य है।
पार्टीशन का एक जोड़ा: {3, 1, 1}, {2, 2, 1}

एल्गोरिदम

checkPartition(set, n)

इनपुट: दिया गया सेट, सेट में तत्वों की संख्या
आउटपुट: सत्य जब दो सबसेट में समान योग के साथ पार्टीशन करना संभव हो

शुरुआत
    sum := सेट में सभी तत्वों का योग
    यदि sum विषम है, तो
        वापस
    (sum/2 + 1 x n+1) ऑर्डर की partTable परिभाषित करें
    0वीं पंक्ति के सभी तत्वों को सत्य पर सेट करें
    0वें कॉलम के सभी तत्वों को असत्य पर सेट करें
    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.