Trong bài toán này, chúng ta phải xây dựng mã C ++ để xác định xem một mảng có thể được chia thành hai mảng con bằng nhau hay không. Ngoài ra, chúng ta phải kiểm tra điều kiện xem tổng của tất cả các phần tử trong cả hai mảng con có hoàn toàn giống nhau hay không. Bài toán phân vùng là một biến thể của Bài toán Tổng tập hợp con, đến lượt nó lại là một biến thể của Bài toán Knapsack. Chúng tôi sẽ sử dụng ngôn ngữ lập trình C ++ để giải quyết vấn đề phân vùng. Chúng ta phải trả về một chuỗi có Có hoặc Không tùy thuộc vào việc điều kiện cụ thể có được đáp ứng hay không.
Đầu vào
arr[] = {6, 4, 8, 12, 15} Đầu ra
Is possible to divide into two subsets of equal sum
Phương pháp giải quyết vấn đề
Mục đích là tìm tổng của tất cả các phần tử trong tập hợp. Khi tổng mảng là số lẻ, chúng ta không thể chia nó thành hai tập hợp. Xác định các tập hợp con có tổng / 2 khi tổng số chẵn. Sử dụng mảng đã cho, điều tra từng phần tử một, sau đó chọn một trong các lựa chọn sau:
-
Tiếp tục đưa mục hiện tại vào tập hợp con, sau đó thêm phần còn lại để đạt được tổng.
-
Khi mục hiện tại đã được xóa khỏi tập hợp con, hãy lặp lại quy trình cho các mục khác.
Cuối cùng, trả về true nếu mục hiện tại được bao gồm hoặc loại trừ trong một tập hợp con; nếu không, trả về false. Đệ quy kết thúc, nếu không còn mục nào nữa hoặc nếu tổng trở thành số âm. Trong trường hợp tổng bằng 0, chúng tôi trả về true, nghĩa là một tập hợp con đã được xác định.
Ví dụ
#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;
} Đầu ra
Is impossible to divide into two subsets of equal sum
Cách tiếp cận 2
Khi tổng các thành phần không quá lớn, vấn đề có thể được xử lý bằng cách sử dụng lập trình động. Một phần mảng 2D [] [] có kích thước (sum / 2 + 1) * (n + 1) có thể được tạo. Chúng tôi cũng có thể xây dựng giải pháp từ dưới lên để mỗi mục nhập đã điền có thuộc tính sau. Chúng tôi có thể giải quyết vấn đề này bằng cách sử dụng mảng 2-D có kích thước (sum / 2 + 1) * (n + 1) thay vì a Kích thước mảng 2-D (sum / 2 + 1) * (n + 1).
Ví dụ
#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;
} Đầu ra
Is impossible to divide into two subsets of equal sum
Kết luận
Trong bài toán này, chúng ta đã học cách giải quyết các vấn đề về phân vùng cùng với mã c ++. Mã này cũng có thể được viết bằng java, python và các ngôn ngữ khác. Chúng tôi đã giải quyết vấn đề phân vùng bằng cách sử dụng mảng đệ quy trong ngôn ngữ lập trình C ++. Nó là một mã cơ bản nhưng có rất nhiều công dụng trong việc giải quyết các vấn đề.