이 문제에서는 배열이 두 개의 동일한 하위 배열로 분할될 수 있는지 여부를 결정하기 위해 C++ 코드를 작성해야 합니다. 또한 두 하위 배열의 모든 요소의 합이 정확히 동일한지 여부를 조건을 확인해야 합니다. 파티셔닝 문제는 부분집합 문제의 변형이며, 이는 다시 배낭 문제의 변형입니다. 파티션 문제를 해결하기 위해 C++ 프로그래밍 언어를 사용할 것입니다. 지정된 조건이 충족되었는지 여부에 따라 Yes 또는 No가 포함된 문자열을 반환해야 합니다.
입력
arr[] = {6, 4, 8, 12, 15} 출력
Is possible to divide into two subsets of equal sum
문제 해결을 위한 접근
목표는 집합에 있는 모든 요소의 합을 찾는 것입니다. 배열 합계가 홀수이면 두 세트로 나눌 수 없습니다. 합계가 짝수일 때 sum/2로 부분 집합을 식별합니다. 주어진 배열을 사용하여 각 요소를 하나씩 조사한 후 다음 항목 중 하나를 선택하십시오.
-
하위 집합에 현재 항목을 계속 포함하고 나머지를 추가하여 합계에 도달합니다.
-
현재 항목이 하위 집합에서 제거되면 다른 항목에 대해 프로세스를 반복합니다.
마지막으로 현재 항목이 하위 집합에 포함되거나 제외되면 true를 반환합니다. 그렇지 않으면 false를 반환합니다. 더 이상 항목이 없거나 합계가 음수가 되면 재귀가 종료됩니다. 합계가 0인 경우 하위 집합이 식별되었음을 의미하는 true를 반환합니다.
예
#include <bits/stdc++.h>
using namespace std;
bool isSubsetSum(int arr[], int n, int sum) {
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;
if (arr[n - 1] > sum)
return isSubsetSum(arr, n - 1, sum);
return isSubsetSum(arr, n - 1, sum) ||
isSubsetSum(arr, n - 1, sum - arr[n - 1]);
}
bool findPartiion(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
if (sum % 2 != 0)
return false;
return isSubsetSum(arr, n, sum / 2);
}
int main() {
int arr[] = {
6,
4,
8,
12,
15
};
int n = sizeof(arr) / sizeof(arr[0]);
if (findPartiion(arr, n) == true)
cout << "Is possible to divide into two subsets " "of equal sum";
else
cout << "Is impossible to divide into two subsets" " of equal sum";
return 0;
} 출력
Is impossible to divide into two subsets of equal sum
접근법 2
구성 요소의 합계가 너무 크지 않으면 동적 프로그래밍을 사용하여 문제를 처리할 수 있습니다. (sum/2 + 1)*(n+1) 크기의 2D 배열 부분[][]을 생성할 수 있습니다. 채워진 각 항목이 다음 속성을 갖도록 아래에서 위로 솔루션을 빌드할 수도 있습니다. (sum/2 + 1)*(n + 1) 크기의 2차원 배열.
예
#include <bits/stdc++.h>
using namespace std;
bool findPartiion(int arr[], int n) {
int sum = 0;
int i, j;
for (i = 0; i < n; i++)
sum += arr[i];
if (sum % 2 != 0)
return false;
bool part[sum / 2 + 1];
for (i = 0; i <= sum / 2; i++) {
part[i] = 0;
}
for (i = 0; i < n; i++) {
for (j = sum / 2; j >= arr[i]; j--){
if (part[j - arr[i]] == 1 || j == arr[i])
part[j] = 1;
}
}
return part[sum / 2];
}
int main() {
int arr[] = {
6,
4,
8,
12,
15
};
int n = sizeof(arr) / sizeof(arr[0]);
if (findPartiion(arr, n) == true)
cout << "Is possible to divide into two subsets of equal " "sum";
else
cout << "Is impossible to divide into two subsets" " of equal sum";
return 0;
} 출력
Is impossible to divide into two subsets of equal sum
결론
이번 문제에서는 C++ 코드와 함께 파티션 문제를 해결하는 방법을 배웠습니다. 이 코드는 Java, python 및 기타 언어로도 작성할 수 있습니다. C++ 프로그래밍 언어에서 재귀 배열을 사용하여 파티션 문제를 해결했습니다. 기본적인 코드지만 문제 해결에 여러 용도가 있습니다.