Hướng dẫn giải của Tài nguyên (đề HSG 12 Phú Thọ 2024-2025)
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Bài cái túi có giới hạn số lượng: tải trọng ~s \le 2000~, ~n~ loại tài nguyên (giá trị ~v_i~, nặng ~w_i~, có ~k_i~ đơn vị), tối đa hóa tổng năng lượng với tổng khối lượng không quá ~s~. Chú ý ~k_i~ lớn tới ~10^9~ nên không thể tách từng đơn vị một cách ngây thơ; mỗi loại chỉ lấy tối đa ~\lfloor s / w_i \rfloor~ đơn vị.
Sub 1: Một loại tài nguyên — ~n = 1~
Lấy nhiều nhất có thể: ~\min(k_1, \lfloor s / w_1 \rfloor)~ đơn vị, kết quả là số đó nhân ~v_1~. Nếu chỉ nộp sub này: đúng 3/20 test.
Sub 2: Tách nhị phân — ~O(n \cdot s \cdot \log s)~, dùng khi ~n \le 100~
Giới hạn ~k_i~ bởi ~\lfloor s / w_i \rfloor~, rồi tách thành các gói có số đơn vị 1, 2, 4, ... và phần dư; mỗi gói là một vật của cái túi 0/1. Nếu chỉ nộp sub này: đúng 20/20 test, nhưng với ~n~ lớn thì chậm.
Sub 3: Gom theo cân nặng — ~O(s^2 \log s)~
Các loại cùng cân nặng ~w~ chỉ cần lấy tối đa ~\lfloor s / w \rfloor~ đơn vị, và nên lấy những đơn vị giá trị lớn nhất trước. Do đó tổng số đơn vị cần xét không quá ~\sum_{w=1}^{s} s / w \approx s \ln s~ (khoảng 16000), rồi chạy cái túi 0/1 thông thường với ~O(s)~ mỗi đơn vị. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu; ~n = 1~ gọi sub1, ~n \le 100~ gọi sub2, còn lại gọi sub3. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int s, n;
long long V[100005], K[100005];
int W[100005];
// Sub 1: n = 1, lấy nhiều nhất có thể
void sub1() {
long long cnt = min(K[1], (long long)(s / W[1]));
printf("%lld\n", cnt * V[1]);
}
static long long dp[2005];
// Sub 2: cái túi có số lượng, tách nhị phân mỗi loại thành các gói 1,2,4,..., O(n * s * log k), dùng khi n <= 100
void sub2() {
for (int i = 1; i <= n; i++) {
long long k = min(K[i], (long long)(s / W[i]));
for (long long p = 1; k > 0; p <<= 1) {
long long c = min(p, k);
k -= c;
long long w = c * W[i], v = c * V[i];
for (int j = s; j >= w; j--) dp[j] = max(dp[j], dp[j - w] + v);
}
}
printf("%lld\n", dp[s]);
}
// Sub 3: gom các loại cùng cân nặng w. Với cân nặng w chỉ lấy tối đa s / w đơn vị, và nên lấy
// những đơn vị giá trị lớn nhất. Tổng số đơn vị sau khi gom <= s * (1 + 1/2 + ... + 1/s) ~ 16000,
// rồi chạy cái túi 0/1 thông thường.
void sub3() {
vector<vector<pair<long long, long long>>> byW(s + 1);
for (int i = 1; i <= n; i++) byW[W[i]].push_back({V[i], K[i]});
for (int w = 1; w <= s; w++) {
auto& vec = byW[w];
if (vec.empty()) continue;
sort(vec.rbegin(), vec.rend()); // giá trị giảm dần
long long cap = s / w;
for (auto& pr : vec) {
long long c = min(pr.second, cap);
cap -= c;
for (long long t = 0; t < c; t++)
for (int j = s; j >= w; j--) dp[j] = max(dp[j], dp[j - w] + pr.first);
if (cap == 0) break;
}
}
printf("%lld\n", dp[s]);
}
int main() {
freopen("CAU4.INP", "r", stdin);
freopen("CAU4.OUT", "w", stdout);
scanf("%d %d", &s, &n);
for (int i = 1; i <= n; i++) scanf("%lld %d %lld", &V[i], &W[i], &K[i]);
if (n == 1) sub1();
else if (n <= 100) sub2();
else sub3();
return 0;
}
Bình luận