Máy ATM (quay lui - nhánh cận)
Xem dạng PDF
Gửi bài giải
Điểm:
2,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Một máy ATM hiện có n (n ≤ 30) tờ tiền có giá trị t[1], t[2].... t[n]. Hãy tìm cách trả ít tờ nhất với số tiên đúng bằng S (các tờ tiền có giá trị bất kỳ và có thể băng nhau, mỗi tờ tiền chỉ được dùng một lần).
Đầu vào: Dòng 1 gồm 2 số nguyên n và s (s ≤ 10^9). Dòng thứ hai chứa n số nguyên t[1], t[2], ..., t[n] (t[i] ≤ 10^9)
Ràng buộc: 1 <= N <= 30; 1 <= S <= 10^9; 1 <= t[i] <= 10^9
Đầu ra: In ra số tờ tiền ít nhất phải trả, nếu không thể tìm được ra kết quả thì in -1.
Input:
6 30
10 4 10 5 8 8
Output:
4
Bình luận
thuật toán dễ hiểu ai cần cho mình 1 vote:
✅ Phân tích:
Vì n ≤ 30 nên không thể dùng quy hoạch động theo tổng S (do S ≤ 10^9 quá lớn).
Tuy nhiên, n nhỏ nên ta có thể dùng Kỹ thuật chia đôi (Meet in the Middle):
Chia mảng thành 2 nửa: A và B.
Sinh tất cả tập con của A và B (gồm cả tổng và số lượng tờ).
Duyệt các tổ hợp từ A và B sao cho tổng của chúng bằng S.
Với mỗi tổ hợp hợp lệ, lưu lại số lượng tờ ít nhất.
🧠 Chi tiết kỹ thuật:
Tập con có thể sinh bằng bitmask (tối đa 2^15 = 32768 phần tử mỗi nửa).
Dùng unordered_map<long long, int> để lưu mapB: với mỗi tổng trong B, lưu số lượng tờ ít nhất để tạo ra tổng đó.
Với mỗi tổng sumA từ nửa A, ta cần tìm S - sumA trong mapB.