Hướng giải của Chia Kẹo Thành Hai Nhóm
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Lời giải: Chia \(N\) hộp kẹo thành hai nhóm có chênh lệch nhỏ nhất
Tư duy
Gọi \(T\) là tổng khối lượng toàn bộ \(N\) hộp kẹo. Khi chọn một tập con có tổng \(s\), nhóm còn lại sẽ có tổng \(T - s\), chênh lệch giữa hai nhóm là \(|T - 2s|\). Như vậy ta chỉ cần tìm \(s\) gần với \(T/2\) nhất.
Thuật giải
Vì \(N \le 20\), ta có thể duyệt mọi tập con thông qua mask (mỗi bit biểu diễn một phần tử được chọn hay không). Có chính xác \(2^N\) tập con.
Với mỗi mask, ta tính tổng dp[mask] bằng cách lấy bit thấp nhất (lsb) của mask và tách thành dp[mask ^ lsb] + a[bit_of_lsb]. Đồng thời cập nhật bestDiff qua từng mask.
Đánh giá độ phức tạp
- Thời gian: \(O(N \cdot 2^N)\) – với \(N = 20\) chỉ khoảng \(2 \cdot 10^7\) phép tính, hoàn toàn nhanh.
- Bộ nhớ: \(O(2^N)\) – chỉ vài MB cho mảng
dp[].
Mã nguồn tham khảo
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n;
if (!(cin >> n)) return 0;
vector<long long> a(n);
long long total = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
total += a[i];
}
// dp[mask] = tổng khối lượng của các phần tử trong mask
int full = 1 << n;
vector<long long> dp(full);
long long bestDiff = total;
for (int mask = 0; mask < full; mask++) {
if (mask == 0) { dp[0] = 0; continue; }
int lsb = mask & -mask; // bit thấp nhất
int bit = __builtin_ctz(lsb); // vị trí bit đó
dp[mask] = dp[mask ^ lsb] + a[bit];
long long diff = llabs(total - 2 * dp[mask]); // chênh lệch
if (diff < bestDiff) bestDiff = diff;
}
cout << bestDiff << "\n";
return 0;
}
Nhận xét