Vấn đề phân vùng

Đối với vấn đề này, một tập hợp nhất định có thể được phân vùng theo cách như vậy, tổng của mỗi tập hợp con là bằng nhau.

Lúc đầu, chúng ta phải tìm tổng của tập hợp đã cho. Nếu nó là chẵn, sau đó có một cơ hội để chia nó thành hai tập hợp. Nếu không, nó không thể được phân chia.

Đối với giá trị chẵn của tổng, sau đó chúng ta sẽ tạo một bảng có tên partTable, bây giờ sử dụng điều kiện sau để giải quyết vấn đề.

partTable [i, j] là true, khi tập con của mảng [0] đến mảng [j-1] có tổng bằng i, ngược lại thì sai.

Đầu vào và Đầu ra

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}

Thuật toán

checkPartition(set, n)

Đầu vào - Tập hợp đã cho, số phần tử trong tập hợp.

Đầu ra - Đúng khi phân hoạch có thể tạo thành hai tập con có tổng bằng nhau.

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

Ví dụ

#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.";
} 

Đầu ra

Given Set can be divided into two subsets of equal sum.