Cho mảng A kích thước N và số T. Amal thi đấu T phút, N bài, bài i tốn A[i] phút. Chọn tập con bài sao cho tổng thời gian ≤ T và lớn nhất có thể.
Ví dụ
Với T=17, A=[2,3,5,7,11], đầu ra 17 (chọn 4 bài đầu: 2+3+5+7=17).
Giải thuật
Bài toán cái balo (knapsack) gặp ở giữa (meet-in-the-middle). Chia mảng thành 2 nửa, tính tất cả tổng tập con của mỗi nửa. Sắp xếp nửa 2. Với mỗi tổng của nửa 1, tìm nhị phân tổng lớn nhất của nửa 2 sao cho tổng ≤ T.
Mã C++
#include <bits/stdc++.h>
using namespace std;
int solve(int t, vector<int> A) {
int n = A.size();
vector<int> b(n / 2), c(n - n / 2);
for (int i = 0; i < n / 2; i++) b[i] = A[i];
for (int i = n / 2; i < n; i++) c[i - n / 2] = A[i];
vector<int> B, C;
for (int bit = 0; bit < (1 << (n / 2)); bit++) {
int p = 0;
for (int i = 0; i < n / 2; i++)
if (bit & (1 << i)) p += b[i];
B.push_back(p);
}
for (int bit = 0; bit < (1 << (n - n / 2)); bit++) {
int p = 0;
for (int i = 0; i < n - n / 2; i++)
if (bit & (1 << i)) p += c[i];
C.push_back(p);
}
int mx = 0;
sort(C.begin(), C.end());
for (int i = 0; i < B.size(); i++) {
if (t - B[i] < 0) continue;
auto itr = upper_bound(C.begin(), C.end(), t - B[i]);
itr--;
mx = max(mx, *itr + B[i]);
}
return mx;
}
int main() {
int T = 17;
vector<int> A = { 2, 3, 5, 7, 11 };
cout << solve(T, A) << endl;
}
Đầu vào / Đầu ra
Input: 17, { 2, 3, 5, 7, 11 }
Output: 17