分区问题
对于此问题，可以以一种方式对给定的集合进行分区，以使每个子集的总和相等。
首先，我们必须找到给定集合的总和。如果是偶数，则有机会将其分为两组。否则，将无法分割。
对于总和的均值，我们将创建一个名为partTable的表，现在使用以下条件解决该问题。
当array[0]到array[j-1]的子集的和等于i时，partTable[i，j]为true，否则为false。
输入输出
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
//以bottonup方式填充分区表
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 << "给定集合可以分为相等总和的两个子集。";
else
cout << "给定集合不能分为相等总和的两个子集。";
}输出结果
给定集合可以分为相等总和的两个子集。