I. Giới thiệu
1. Phát biểu bài toán
Trong các kì thi lập trình, có không ít bài toán yêu cầu chúng ta phải tìm toàn bộ nghiệm. Đôi khi, chúng ta gặp phải những bài toán bắt buộc phải duyệt qua tất cả các cấu hình để tìm ra đáp án thỏa mãn yêu cầu.
Hãy xem xét một ví dụ sau:
Cho một tập hợp A gồm n phần tử a1, a2, …, an. Hãy xác định có bao nhiêu tập hợp con của A có tổng đúng bằng giá trị s cho trước?
Input:
- Dòng đầu tiên chứa hai số nguyên dương n và s.
- Dòng thứ hai chứa n số nguyên dương a1, a2, …, an phân tách nhau bởi dấu cách.
Ràng buộc:
- 1 ≤ n ≤ 40.
- 1 ≤ s ≤ 10^18.
- 1 ≤ a_i ≤ 10^12; ∀i: 1 ≤ i ≤ n.
Output:
- Một số nguyên là số lượng tập hợp con tìm được.
Ví dụ đầu vào:
5 10
1 9 8 2 1Kết quả đầu ra:
42. Kỹ thuật Duyệt Phân Đôi Tập Hợp
Ý tưởng
Với những loại bài toán như trên, phương pháp thông thường nhất là sử dụng quay lui để thử chọn ra tất cả các tập hợp khác nhau và tính tổng của chúng. Tuy nhiên, độ phức tạp của thuật toán này có thể lên tới O(2^40), khiến máy tính khó có thể hoàn thành trong thời gian cho phép. Đó là lý do xuất hiện kỹ thuật Duyệt Phân Đôi Tập Hợp.
Kỹ thuật này được áp dụng cho những bài toán có kích thước nhỏ, nhưng không đủ nhỏ để xử lý bằng quy trình duyệt toàn bộ nghiệm thông thường. Chúng ta sẽ chia tập hợp ban đầu thành hai phần, duyệt sinh tất cả các cấu hình ở mỗi phần rồi kết hợp hai bên lại để tạo thành nghiệm của bài toán.
Quy trình thực hiện
- Bước 1: Chia tập hợp A thành hai tập con: A[1...n/2] và A[n/2+1...n].
- Bước 2: Sử dụng quay lui để sinh tất cả các tổng ở mỗi tập con, lưu vào hai mảng sum_left và sum_right. Đừng quên lưu cả tổng 0 (không chọn phần tử nào) để xử lý tiếp theo.
- Bước 3: Sắp xếp lại các giá trị trong mảng sum_left tăng dần.
- Bước 4: Duyệt qua các tổng s1 trong mảng sum_right. Ứng với mỗi tổng s1, xác định xem có bao nhiêu tổng s2 trong sum_left thỏa mãn: s1 + s2 = s. Sử dụng tìm kiếm nhị phân để phát hiện.
Tối ưu độ phức tạp
Với kỹ thuật này, độ phức tạp của giải thuật sẽ giảm chỉ còn O(2^(n/2) * log(2^(n/2))), hoàn toàn phù hợp với thời gian chạy yêu cầu trong các kì thi lập trình.
Cài đặt mã nguồn
Đoạn mã ví dụ được cung cấp dưới đây là một cài đặt hoàn chỉnh cho vấn đề đã nêu:
cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
void enter(int &n, int &s, vector<int> &a) {
cin >> n >> s;
a.resize(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
}
void generate_set(int i, int limit, int sum, vector<int> &a, vector<int> &subset_sum) {
for (int j = 0; j <= 1; ++j) {
sum += a[i] * j;
if (i == limit)
subset_sum.push_back(sum);
else
generate_set(i + 1, limit, sum, a, subset_sum);
sum -= a[i] * j;
}
}
void solution(int n, int s, vector<int> &a) {
vector<int> sum_left, sum_right;
generate_set(1, (n + 1) / 2, 0, a, sum_left);
generate_set((n + 1) / 2 + 1, n, 0, a, sum_right);
sort(sum_left.begin(), sum_left.end());
int res = 0;
for (int cur_s: sum_right) {
if (cur_s > s) continue;
auto p = equal_range(sum_left.begin(), sum_left.end(), s - cur_s);
if (*p.first == s - cur_s)
res += distance(p.first, p.second);
}
cout << res;
}
int main() {
int n, s;
vector<int> a;
enter(n, s, a);
solution(n, s, a);
return 0;
}II. Một số bài toán minh họa
1. Tổng vector
Đề bài
Trên mặt phẳng tọa độ Oxy, cho trước n vector. Mỗi vector được định nghĩa bởi hai chỉ số x và y. Cần chọn ra một số vector sao cho tổng của chúng tạo ra vector (u, v).
Quy trình thực hiện
Sử dụng kỹ thuật Duyệt Phân Đôi Tập Hợp để sinh tất cả các tổng vector từ hai nửa của tập hợp các vector đã cho, lưu vào hai map để đếm số lần xuất hiện của các vector tổng ở mỗi phần. Sau đó, duyệt qua các vector tổng và tìm xem có bao nhiêu vector ứng với yêu cầu từ bản đồ đã tạo.
2. Đếm ước số
Đề bài
Cho một số nguyên dương n được phân tích thành thừa số nguyên tố. Hãy xác định số lượng ước số của n nằm trong khoảng [A, B].
Quy trình thực hiện
Sử dụng kỹ thuật Duyệt Phân Đôi Tập Hợp để sinh ra các tích các số nguyên tố. Sau đó, kết hợp các tích này để tìm ra số lượng ước trong đoạn [A, B].
