VOJ - DTTUI2
Source: DTTUI2
Tags: Dynamic Programming
Problem:
Cho một cái túi có tải trọng tối đa là M và N loại đồ vật, món đồ loại i có trọng lượng là W[i], giá trị là C[i] và số lượng là A[i]. Tìm cách chứa các món đồ sao cho tổng giá trị trong túi là lớn nhất mà tổng trọng lượng không vượt quá M.
1 ≤ N ≤ 100.
1 ≤ M ≤ 1e4.
1 ≤ W[i], C[i], A[i] ≤ 1e3.
Ví dụ:
Input:
3 4
1 4 2
2 7 2
3 6 1
Output:
15
Explanation:
Chọn 2 món đồ loại 1 và 1 món đồ loại 2.
Solution:
Đây là một toán tương đối khó. Tên tiếng Anh: The integral bounded knapsack problem. Có thể tìm thấy trên blog của Petr, ghi khá ngắn gọn nhưng đầy đủ những ý chính. Ngoài ra, có thể tham khảo trên blog của dhruvbird, ghi chi tiết hơn nhiều. Ở đây mình sẽ viết lại những gì mình hiểu sau khi dành thời gian nghiên cứu blog của 2 ông :D Mọi thắc mắc và góp ý xin hãy để lại ở phần phản hồi ♥
Approach 1:
Dễ dàng nhìn ra được công thức DP trong O(N.M.max(A[i])) như sau:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + C[i], ..., dp[i - 1][j - A[i] * W[i]] + A[i] * C[i])
Mình sẽ không giải thích thêm về công thức này nữa.
Approach 2:
Ở hướng tiếp cận thứ 2 này sẽ không giúp ích gì cho hướng tiếp cận thứ 3, bạn có thể cân nhắc bỏ qua hướng tiếp cận này.
Câu hỏi được đặt ra là, tại sao chúng ta không tạo một mảng mới gồm A[1] + A[2] + ... + A[N] phần tử bằng cách tách mỗi loại i ra thành A[i] món đồ luôn? Câu trả lời rất rõ ràng nhận thấy, đó là chúng ta sẽ TLE khi DP O(N.M) với N mới (thậm chí còn MLE nữa). Nhưng đây chính là hướng suy nghĩ chính của hướng tiếp cận này.
Để ý rằng, việc tách mỗi loại i thành A[i] món đồ sẽ trông khá đần khi với mỗi tải trọng M, ta phải tính dp[M - W[i]] A[i] lần. Vậy để giải quyết cho khỏi đần nữa, ta sẽ tách A[i] thành tổng các lũy thừa của 2 như sau: A[i] = 2^0 + 2^1 + ... + 2^floor(log2(A[i])) + x. Sau đấy thêm vào mảng mới món đồ có trọng lượng và giá trị là (W[i] * 2^0, C[i] * 2^0), (W[i] * 2^1, C[i] * 2^1), ...
Ví dụ: ta có món đồ trọng lượng W = 3, giá trị C = 1 và số lượng A = 10, ta có thể tách món đồ này thành 4 món đồ mới có trọng lượng và giá trị mới như sau (3, 1); (6, 2); (12, 4) và (9, 3) tương ứng với từng số hạng 2^0; 2^1; 2^2 và 3.
Có vẻ khó hiểu phải không, để mình giải thích. Ở hướng tiếp cận 1, giả sử dp[i][j] = dp[i - 1][j - k * W[i]] + k * C[i], ở đây k là số lượng món đồ loại i thích hợp để tổng giá trị là lớn nhất, vậy ta có thể tách k = x0 * 2^0 + x1 * 2^1 + ... Vậy khi chúng ta tách A[i] món đồ ra như trên, ta sẽ dễ dàng tìm được giá trị k món đồ trong log. Ví dụ k = 5, ta có thể cộng món đồ mang giá trị tương ứng số hạng 2^0 và 2^2 lại.
Như vậy với cách trên ta dễ dàng thu gọn việc trông có vẻ ngớ ngẩn là tách ra A[i] món đồ thành tách ra log2(A[i]) món đồ và dễ dàng DP trên đấy với độ phức tạp O(N.M.log2(max(A[i]))).
Code: (vì độ phức tạp của cách này hình như vẫn vượt quá time limt 0.2s nên mình vẫn chưa AC, chỉ được 21.43 điểm thôi, nên không biết là code có đúng không nhưng thôi cứ thêm vào cho mấy bạn tham khảo :D mình sẽ update lại khi có thể test code kỹ hơn)
#include <iostream>
#include <vector>
using namespace std;
int n, m, dp[115][10015];
vector <pair <int, int>> x;
int main() {
cin >> n >> m;
x.push_back({0, 0});
for (int i = 0; i < n; i++) {
int w, v, a; cin >> w >> v >> a;
for (int b = 1; a > b; a -= b, b <<= 1)
x.push_back({w * b, v * b});
x.push_back({w * a, v * a});
}
for (int i = 1; i < x.size(); i++)
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= x[i].first)
dp[i][j] = max(dp[i][j], dp[i - 1][j - x[i].first] + x[i].second);
}
cout << dp[x.size() - 1][m];
}
Approach 3:
Bây giờ, tưởng tượng A[i] = +∞, khi này mỗi bài toán dp[i][j] sẽ liên kết với dp[i - 1][j - k * W[i]] với k = 0...j / W[i]. Khi này ta có W[i] bài toán con riêng biệt như sau:
Ví dụ M = 10, W[i] = 3:
* dp[0] - dp[3] - dp[6] - dp[9]
* dp[1] - dp[4] - dp[7] - dp[10]
* dp[2] - dp[5] - dp[8]
Quay lại với ràng buộc A[i] là một số cụ thể, coi mỗi bài toán con lúc này là một dãy số riêng biệt, giả sử lấy ví dụ trên, ta có A[i] = 2, đứng tại dp[10] là phần tử thứ 4, có phải ta chỉ xét từ phần tử thứ 2 (dp[4]) trở lên thôi đúng không? (vì ta có thể có thể chọn 0 món đồ loại i nữa nên cần xét A[i] + 1 phần tử kề nhau)
Rồi, bây giờ xem một bài toán con bất kỳ trên là dãy số X[1], X[2], ..., X[M / W[i]] đi. Ta nhận thấy xét tại một vị trí k = 1..M / W[i], ta cần tính max(X[k], X[k - 1] + C[i], ..., X[k - A[i]] + A[i] * C[i]), làm sao để tính nhanh đây? Đầu tiên ta tạo một mảng Y[k] = X[k] - k * C[i], vậy lúc này cái ta cần tính mới đó là
max(Y[k] + k * C[i], Y[k - 1] + (k - 1) * C[i] + C[i], ..., Y[k - A[i]] + (k - A[i]) * C[i] + A[i] * C[i])
= k * C[i] + max(Y[k], Y[k - 1], ..., Y[k - A[i]])
Tadaaa *insert pháo bông bay* ta có một mảng Y không phụ thuộc vào vị trí đang xét, ta có thể tìm max đoạn [k - A[i], k] trong (gần như) O(1) bằng DP hoặc deque.
Độ phức tạp tổng cộng của cách này là O(2.N.M)
Code:
#include <iostream>
#include <queue>
using namespace std;
int n, m, dp[10015], tmp[10015];
deque <int> max_val[10015];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int w, v, a; cin >> w >> v >> a;
for (int j = 0; j <= m; j++) {
tmp[j] = dp[j] - v * j / w;
if (j / w) {
while (!max_val[j % w].empty() && tmp[max_val[j % w].back()] <= tmp[j])
max_val[j % w].pop_back();
while (!max_val[j % w].empty() && max_val[j % w].front() / w + a < j / w)
max_val[j % w].pop_front();
max_val[j % w].push_back(j);
dp[j] = tmp[max_val[j % w].front()] + v * j / w;
}
else max_val[j].clear(), max_val[j].push_back(j);
}
}
cout << dp[m];
}
Tags: Dynamic Programming
Problem:
Cho một cái túi có tải trọng tối đa là M và N loại đồ vật, món đồ loại i có trọng lượng là W[i], giá trị là C[i] và số lượng là A[i]. Tìm cách chứa các món đồ sao cho tổng giá trị trong túi là lớn nhất mà tổng trọng lượng không vượt quá M.
1 ≤ N ≤ 100.
1 ≤ M ≤ 1e4.
1 ≤ W[i], C[i], A[i] ≤ 1e3.
Ví dụ:
Input:
3 4
1 4 2
2 7 2
3 6 1
Output:
15
Explanation:
Chọn 2 món đồ loại 1 và 1 món đồ loại 2.
Solution:
Đây là một toán tương đối khó. Tên tiếng Anh: The integral bounded knapsack problem. Có thể tìm thấy trên blog của Petr, ghi khá ngắn gọn nhưng đầy đủ những ý chính. Ngoài ra, có thể tham khảo trên blog của dhruvbird, ghi chi tiết hơn nhiều. Ở đây mình sẽ viết lại những gì mình hiểu sau khi dành thời gian nghiên cứu blog của 2 ông :D Mọi thắc mắc và góp ý xin hãy để lại ở phần phản hồi ♥
Approach 1:
Dễ dàng nhìn ra được công thức DP trong O(N.M.max(A[i])) như sau:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + C[i], ..., dp[i - 1][j - A[i] * W[i]] + A[i] * C[i])
Mình sẽ không giải thích thêm về công thức này nữa.
Approach 2:
Ở hướng tiếp cận thứ 2 này sẽ không giúp ích gì cho hướng tiếp cận thứ 3, bạn có thể cân nhắc bỏ qua hướng tiếp cận này.
Câu hỏi được đặt ra là, tại sao chúng ta không tạo một mảng mới gồm A[1] + A[2] + ... + A[N] phần tử bằng cách tách mỗi loại i ra thành A[i] món đồ luôn? Câu trả lời rất rõ ràng nhận thấy, đó là chúng ta sẽ TLE khi DP O(N.M) với N mới (thậm chí còn MLE nữa). Nhưng đây chính là hướng suy nghĩ chính của hướng tiếp cận này.
Để ý rằng, việc tách mỗi loại i thành A[i] món đồ sẽ trông khá đần khi với mỗi tải trọng M, ta phải tính dp[M - W[i]] A[i] lần. Vậy để giải quyết cho khỏi đần nữa, ta sẽ tách A[i] thành tổng các lũy thừa của 2 như sau: A[i] = 2^0 + 2^1 + ... + 2^floor(log2(A[i])) + x. Sau đấy thêm vào mảng mới món đồ có trọng lượng và giá trị là (W[i] * 2^0, C[i] * 2^0), (W[i] * 2^1, C[i] * 2^1), ...
Ví dụ: ta có món đồ trọng lượng W = 3, giá trị C = 1 và số lượng A = 10, ta có thể tách món đồ này thành 4 món đồ mới có trọng lượng và giá trị mới như sau (3, 1); (6, 2); (12, 4) và (9, 3) tương ứng với từng số hạng 2^0; 2^1; 2^2 và 3.
Có vẻ khó hiểu phải không, để mình giải thích. Ở hướng tiếp cận 1, giả sử dp[i][j] = dp[i - 1][j - k * W[i]] + k * C[i], ở đây k là số lượng món đồ loại i thích hợp để tổng giá trị là lớn nhất, vậy ta có thể tách k = x0 * 2^0 + x1 * 2^1 + ... Vậy khi chúng ta tách A[i] món đồ ra như trên, ta sẽ dễ dàng tìm được giá trị k món đồ trong log. Ví dụ k = 5, ta có thể cộng món đồ mang giá trị tương ứng số hạng 2^0 và 2^2 lại.
Như vậy với cách trên ta dễ dàng thu gọn việc trông có vẻ ngớ ngẩn là tách ra A[i] món đồ thành tách ra log2(A[i]) món đồ và dễ dàng DP trên đấy với độ phức tạp O(N.M.log2(max(A[i]))).
Code: (vì độ phức tạp của cách này hình như vẫn vượt quá time limt 0.2s nên mình vẫn chưa AC, chỉ được 21.43 điểm thôi, nên không biết là code có đúng không nhưng thôi cứ thêm vào cho mấy bạn tham khảo :D mình sẽ update lại khi có thể test code kỹ hơn)
#include <iostream>
#include <vector>
using namespace std;
int n, m, dp[115][10015];
vector <pair <int, int>> x;
int main() {
cin >> n >> m;
x.push_back({0, 0});
for (int i = 0; i < n; i++) {
int w, v, a; cin >> w >> v >> a;
for (int b = 1; a > b; a -= b, b <<= 1)
x.push_back({w * b, v * b});
x.push_back({w * a, v * a});
}
for (int i = 1; i < x.size(); i++)
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= x[i].first)
dp[i][j] = max(dp[i][j], dp[i - 1][j - x[i].first] + x[i].second);
}
cout << dp[x.size() - 1][m];
}
Approach 3:
Bây giờ, tưởng tượng A[i] = +∞, khi này mỗi bài toán dp[i][j] sẽ liên kết với dp[i - 1][j - k * W[i]] với k = 0...j / W[i]. Khi này ta có W[i] bài toán con riêng biệt như sau:
Ví dụ M = 10, W[i] = 3:
* dp[0] - dp[3] - dp[6] - dp[9]
* dp[1] - dp[4] - dp[7] - dp[10]
* dp[2] - dp[5] - dp[8]
Quay lại với ràng buộc A[i] là một số cụ thể, coi mỗi bài toán con lúc này là một dãy số riêng biệt, giả sử lấy ví dụ trên, ta có A[i] = 2, đứng tại dp[10] là phần tử thứ 4, có phải ta chỉ xét từ phần tử thứ 2 (dp[4]) trở lên thôi đúng không? (vì ta có thể có thể chọn 0 món đồ loại i nữa nên cần xét A[i] + 1 phần tử kề nhau)
Rồi, bây giờ xem một bài toán con bất kỳ trên là dãy số X[1], X[2], ..., X[M / W[i]] đi. Ta nhận thấy xét tại một vị trí k = 1..M / W[i], ta cần tính max(X[k], X[k - 1] + C[i], ..., X[k - A[i]] + A[i] * C[i]), làm sao để tính nhanh đây? Đầu tiên ta tạo một mảng Y[k] = X[k] - k * C[i], vậy lúc này cái ta cần tính mới đó là
max(Y[k] + k * C[i], Y[k - 1] + (k - 1) * C[i] + C[i], ..., Y[k - A[i]] + (k - A[i]) * C[i] + A[i] * C[i])
= k * C[i] + max(Y[k], Y[k - 1], ..., Y[k - A[i]])
Tadaaa *insert pháo bông bay* ta có một mảng Y không phụ thuộc vào vị trí đang xét, ta có thể tìm max đoạn [k - A[i], k] trong (gần như) O(1) bằng DP hoặc deque.
Độ phức tạp tổng cộng của cách này là O(2.N.M)
Code:
#include <iostream>
#include <queue>
using namespace std;
int n, m, dp[10015], tmp[10015];
deque <int> max_val[10015];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int w, v, a; cin >> w >> v >> a;
for (int j = 0; j <= m; j++) {
tmp[j] = dp[j] - v * j / w;
if (j / w) {
while (!max_val[j % w].empty() && tmp[max_val[j % w].back()] <= tmp[j])
max_val[j % w].pop_back();
while (!max_val[j % w].empty() && max_val[j % w].front() / w + a < j / w)
max_val[j % w].pop_front();
max_val[j % w].push_back(j);
dp[j] = tmp[max_val[j % w].front()] + v * j / w;
}
else max_val[j].clear(), max_val[j].push_back(j);
}
}
cout << dp[m];
}
Nhận xét
Đăng nhận xét