이 문제에서 주어진 집합은 각 부분 집합의 합이 같은 방식으로 분할될 수 있습니다.
먼저 주어진 집합의 합을 찾아야 합니다. 짝수이면 두 세트로 나눌 기회가 있습니다. 그렇지 않으면 나눌 수 없습니다.
합계 값이 짝수인 경우 partTable이라는 테이블을 만들고 이제 다음 조건을 사용하여 문제를 해결합니다.
partTable[i, j]는 array[0]에서 array[j-1]까지의 부분집합이 i와 같을 때 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)
입력 - 주어진 집합, 집합의 요소 수입니다.
출력 - 분할이 동일한 합계의 두 부분집합을 만드는 것이 가능할 때 참입니다.
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.