ปัญหาพาร์ทิชัน

สำหรับปัญหานี้ ชุดที่กำหนดสามารถแบ่งได้ในลักษณะนี้ ผลรวมของแต่ละชุดย่อยจะเท่ากัน

ขั้นแรกเราต้องหาผลรวมของเซตที่ให้มา ถ้าเท่ากันก็มีโอกาสแบ่งเป็นสองชุด มิเช่นนั้นจะแบ่งแยกไม่ได้

สำหรับค่าที่เท่ากันของผลรวม เราจะสร้างตารางชื่อ 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)

ป้อนข้อมูล - ชุดที่กำหนด จำนวนองค์ประกอบในชุด

ผลลัพธ์ − True เมื่อแบ่งพาร์ติชั่นได้สองชุดย่อยของผลรวมที่เท่ากัน

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.