Hướng dẫn giải của Tối ưu doanh thu cửa hàng
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Editorial for ptit040: Tối ưu doanh thu cửa hàng
Hiểu bài toán
Bài toán yêu cầu chọn các mặt hàng từ kho sao cho tổng khối lượng bằng đúng P và số lượng các loại mặt hàng khác nhau (mỗi loại mặt hàng chỉ được tính 1 nếu chọn ít nhất 1 sản phẩm của loại đó) là lớn nhất. Mỗi loại mặt hàng có số lượng hạn chế k. Với N <= 20, P <= 5000, đây là bài toán quy hoạch động dạng túi đồ (Knapsack) biến thể.
Các cách tiếp cận
Cách Quy hoạch động cơ bản (Knapsack 0-1)
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, P;
cin >> N >> P;
vector<int> k(N), m(N);
for (int i = 0; i < N; i++) {
cin >> k[i] >> m[i];
}
// dp[j] là số lượng loại mặt hàng khác nhau lớn nhất để đạt được khối lượng j
// Khởi tạo -1 (không thể đạt được)
vector<int> dp(P + 1, -1);
dp[0] = 0;
for (int i = 0; i < N; i++) {
// Duyệt ngược để tránh sử dụng cùng một loại nhiều lần trong một bước
// Tuy nhiên do điều kiện 't >= 1' nên duyệt xuôi hay ngược đều được nếu logic đúng
vector<int> next_dp = dp;
for (int j = 0; j <= P; j++) {
if (dp[j] == -1) continue;
// Thử chọn từ 1 đến k[i] sản phẩm của loại i
for (int t = 1; t <= k[i]; t++) {
int next_weight = j + t * m[i];
if (next_weight > P) break;
// Nếu chọn ít nhất 1 sản phẩm, số loại khác nhau tăng 1
next_dp[next_weight] = max(next_dp[next_weight], dp[j] + 1);
}
}
dp = next_dp;
}
cout << dp[P] << endl;
return 0;
}
- Time Complexity: O(N * P * K) ~ 20 * 5000 * 20 = 2 * 10^6
- Space Complexity: O(P) ~ 5000
Sử dụng quy hoạch động dạng mảng 1 chiều. dp[j] lưu số loại hàng khác nhau最大值 để đạt khối lượng j. Với mỗi loại hàng, ta thử các cách chọn từ 1 đến k sản phẩm và cập nhật dp. Do chỉ cần tối ưu số lượng loại hàng (không cần biết cụ thể loại nào), ta có thể cộng dồn điểm số (mỗi loại chọn >0 cộng 1 điểm).
Cách Quy hoạch động tối ưu (Cập nhật trực tiếp)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, P;
cin >> N >> P;
vector<int> k(N), m(N);
for (int i = 0; i < N; i++) {
cin >> k[i] >> m[i];
}
const int NEG = -1e9;
vector<int> dp(P + 1, NEG);
dp[0] = 0;
for (int i = 0; i < N; i++) {
vector<int> new_dp = dp;
for (int j = 0; j <= P; j++) {
if (dp[j] < 0) continue;
for (int t = 1; t <= k[i]; t++) {
int nj = j + t * m[i];
if (nj > P) break;
new_dp[nj] = max(new_dp[nj], dp[j] + 1);
}
}
dp = new_dp;
}
if (dp[P] < 0) cout << -1;
else cout << dp[P];
return 0;
}
- Time Complexity: O(N * P * K)
- Space Complexity: O(P)
Đây là phiên bản tối ưu của Solution 1 và 3. Sử dụng mảng new_dp để lưu kết quả của bước hiện tại, tránh việc cập nhật lại chính nó (tránh nhầm lẫn logic 0-1 knapsack). Với mỗi trạng thái dp[j] hợp lệ, ta thử thêm vào t sản phẩm loại i. Nếu t >= 1, ta cộng thêm 1 vào số loại hàng khác nhau.
Cách Quy hoạch động 2 chiều
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, p;
cin >> n >> p;
vector<int> k(n + 1), m(n + 1);
for (int i = 1; i <= n; i++) {
cin >> k[i] >> m[i];
}
const int inf = 1e9;
// dp[i][j]: số loại hàng max khi xét đến i loại hàng và khối lượng j
vector<vector<int>> dp(n + 1, vector<int>(p + 1, -inf));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= p; j++) {
// Không chọn loại i
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
// Chọn t sản phẩm loại i
for (int t = 1; t <= k[i]; t++) {
if (j >= m[i] * t) {
if (dp[i - 1][j - m[i] * t] != -inf) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - m[i] * t] + 1);
}
}
}
}
}
if (dp[n][p] == -inf) cout << -1 << endl;
else cout << dp[n][p] << endl;
return 0;
}
- Time Complexity: O(N * P * K)
- Space Complexity: O(N * P)
Sử dụng mảng 2 chiều để lưu trạng thái. Dễ hiểu hơn về transitions giữa các bước. dp[i][j] được tính dựa trên các giá trị của dp[i-1]. Logic tương tự như các cách trên: cộng 1 điểm nếu chọn ít nhất 1 sản phẩm.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * P * K) ~ 20 * 5000 * 20 = 2 * 10^6 | O(P) ~ 5000 | Quy hoạch động cơ bản (Knapsack 0-1) |
| 2 | O(N * P * K) | O(P) | Quy hoạch động tối ưu (Cập nhật trực tiếp) |
| 3 | O(N * P * K) | O(N * P) | Quy hoạch động 2 chiều |
Bài học kinh nghiệm
- Bài toán có thể chuyển hóa thành bài toán Knapsack biến thể: thay vì cộng trọng lượng, ta cộng 'điểm' là số lượng loại hàng khác nhau.
- Vì ta chỉ cần đếm số loại hàng khác nhau, ta chỉ cần quan tâm đến việc có chọn loại hàng đó hay không (và chọn bao nhiêu cái để đạt trọng lượng). Việc chọn nhiều cái cùng loại không làm tăng điểm.
- Do N nhỏ (20) nhưng P lớn (5000), giải pháp duyệt tất cả các tổ hợp (2^N hoặc nhiều hơn) là không khả thi. Quy hoạch động với độ phức tạp O(NPK) là tối ưu.
Lỗi thường gặp
- Lỗi logic khi cập nhật dp: Nếu duyệt cùng một mảng dp và cập nhật trực tiếp, ta có thể vô tình sử dụng một loại hàng nhiều lần trong cùng một bước (dù bài này là đa túi đồ, nhưng do ta cộng 1 điểm/lần chọn, cần đảm bảo không double count). Cách dùng mảng 2 chiều hoặc mảng mới (next_dp) là an toàn nhất.
- Quên xử lý trường hợp không có cách chọn nào (output -1): Cần khởi tạo dp với giá trị âm vô cùng (NEG) hoặc -1 và kiểm tra giá trị cuối cùng.
- Bỏ qua trường hợp không chọn gì (t=0): Cần phải copy trạng thái trước đó vào trạng thái hiện tại trước khi thử các giá trị t >= 1 để đảm bảo có thể không chọn loại hàng đó.
Bình luận