Thiết Lập Ký Hiệu
Để đảm bảo tính thống nhất trong các phần phân tích dưới đây, chúng ta định nghĩa các biến như sau:
- n: Tổng số nhóm hoặc loại vật phẩm.
- C: Giới hạn dung tích của túi (sức chứa).
- weight[i]: Khối lượng tiêu hao của vật phẩm loại i.
- value[i]: Giá trị thu được khi lấy vật phẩm loại i.
- quantity[i]: Số lượng vật phẩm loại i có thể sử dụng.
- dp[k]: Max value (hoặc số cách) đạt được với dung tích k.
Bài Toán 0/1 Xách Túi
Trường hợp này giả định mỗi loại vật phẩm có sẵn chính xác một chiếc (quantity[i] == 1). Để tránh trường hợp một vật phẩm được tính vào nhiều lần trong cùng một vòng lặp cập nhật, chúng ta bắt buộc phải lặp qua các mức dung tích theo thứ tự giảm dần.
void processZeroOneKnapsack(int numItems, int bagCapacity, const vector& itemWeights, const vector& itemValues, vector& dpState) {
for (int idx = 0; idx < numItems; ++idx) {
int w = itemWeights[idx];
int val = itemValues[idx];
// Duyệt ngược từ sức chứa lớn nhất đến trọng lượng vật phẩm
for (int cap = bagCapacity; cap >= w; --cap) {
dpState[cap] = max(dpState[cap], dpState[cap - w] + val);
}
}
}Bài Toán Xách Túi Hoàn Hảo
Khi số lượng mỗi loại vật phẩm là vô hạn (quantity[i] = ∞), ta có thể lựa chọn lại vật phẩm đã xét trong cùng một vòng lặp. Điều này cho phép lặp theo chiều tăng dần của dung tích.
void processCompleteKnapsack(int numItems, int bagCapacity, const vector& itemWeights, const vector& itemValues, vector& dpState) {
for (int idx = 0; idx < numItems; ++idx) {
int w = itemWeights[idx];
int val = itemValues[idx];
// Duyệt thuận, cho phép tái sử dụng vật phẩm cùng loại
for (int cap = w; cap <= bagCapacity; ++cap) {
dpState[cap] = max(dpState[cap], dpState[cap - w] + val);
}
}
}Xử Lý Dạng Đếm Và Giới Hạn Số Lượng
Đối với bài toán khi số lượng vật phẩm bị giới hạn (quantity[i] = K), ta cần áp dụng các kỹ thuật tối ưu để tránh độ phức tạp O(n * C * K).
Tối Ưu Hàng Đợi Đơn Điệu (Monotonic Queue)
Hàm chuyển trạng thái có dạng dp[j] = max(dp[j - k*w] + k*v). Nếu xét các dung tích có cùng phần dư khi chia cho w, bài toán trở thành tìm giá trị cực đại trong một cửa sổ trượt có độ dài K. Chúng ta cần lưu trữ trạng thái mảng trước khi cập nhật để đảm bảo tính chính xác của việc chuyển trạng thái.
#include <deque>
#include <vector>
using namespace std;
void optimizeWithDeque(int totalItems, int maxCap, const vector& wt, const vector& vl, const vector& qty, vector& currentDp) {
int capacity = maxCap + 1;
vector previousDp = currentDp; // Sao chép trạng thái cũ
for (int i = 0; i < totalItems; ++i) {
int w = wt[i];
int v = vl[i];
int limit = qty[i];
// Chia nhỏ theo phần dư modulo w
for (int r = 0; r < w; ++r) {
deque<int> window; // Lưu trữ chỉ số
for (int j = r; j <= maxCap; j += w) {
int k = (j - r) / w; // Vị trí trong dãy tương đương
// Đảm bảo độ dài cửa sổ không vượt quá số lượng cho phép
while (!window.empty() && k - window.front() > limit) {
window.pop_front();
}
// Cập nhật dp nếu có phần tử khả dụng trong hàng đợi
if (!window.empty()) {
int bestIdx = window.front();
int prevVal = previousDp[bestIdx];
int diffK = k - (bestIdx - r) / w;
currentDp[j] = max(currentDp[j], prevVal + diffK * v);
}
// Duy trì tính đơn điệu giảm trong hàng đợi
long long newVal = previousDp[j] - (long long)k * v;
while (!window.empty()) {
int backIdx = window.back();
int backK = (backIdx - r) / w;
long long backVal = previousDp[backIdx] - (long long)backK * v;
if (backVal <= newVal) {
window.pop_back();
} else {
break;
}
}
window.push_back(j);
}
}
}
}Sử Dụng Cộng Dồn Tiền Tố (Prefix Sum)
Khi bài toán tập trung vào đếm số phương án thay vì tối đa hóa giá trị, chúng ta có thể dùng mảng tiền tố để tính nhanh tổng trong khoảng. Với mỗi vị trí j, tập các giá trị cha nó bao gồm những chỉ số có cùng phần dư modulo w nằm trong đoạn [j - K*w, j].
const int MOD = 1e9 + 7;
void solveCountingViaPrefix(int items, int bound, const vector& weights, vector& waysCount) {
vector tempSum(bound + 1, 0);
for (int i = 1; i <= items; ++i) {
int w = weights[i];
// Bước 1: Xây dựng mảng cộng dồn từ hàng trước
for (int j = 0; j <= bound; ++j) {
if (j >= w) {
tempSum[j] = (tempSum[j - w] + waysCount[j]) % MOD;
} else {
tempSum[j] = waysCount[j];
}
}
// Bước 2: Trừ đi phần ngoài khoảng cho phép
for (int j = 0; j <= bound; ++j) {
int removeEdge = j - (limit + 1) * w;
if (removeEdge < 0) {
waysCount[j] = tempSum[j];
} else {
waysCount[j] = (tempSum[j] - tempSum[removeEdge] + MOD) % MOD;
}
}
}
}Bài Toán Đặc Biệt Và Ứng Dụng Trên Cây
Các biến thể mở rộng thường gặp khi tham số đầu vào khác biệt hoàn toàn hoặc cấu trúc dữ liệu phức tạp.
Trọng Lượng Hoặc Giá Trị Cực Lớn
Nếu w[i] quá lớn so với sức chứa nhưng v[i] lại nhỏ, ta nên đổi trục bài toán: thay vì tính giá trị theo dung tích, hãy tính dung tích nhỏ nhất để đạt được giá trị X. Một trường hợp đặc biệt là w[i] = a * 2^b cho phép tối ưu hóa thông qua biểu diễn nhị phân của trọng lượng.
Quy Hoạch Động Trên Cây (Tree DP Optimization)
Xét bài toán mà nếu chọn nút con x, tất cả các nút tổ tiên của x cũng phải được chọn. Giải pháp duyệt cây thông thường có độ phức tạp O(n*m^2).
Sử dụng thứ tự DFS (Depth First Order - DFN), ta ánh xạ cây thành một mảng tuyến tính. Khoảng thời gian con của một nút trong thứ tự DFN là một đoạn liên tiếp.
Nếu quyết định không chọn nút gốc của một nhánh, toàn bộ nhánh con đó đều bị loại bỏ, cho phép ta nhảy trực tiếp từ vị trí hiện tại đến ngay sau cuối của nhánh con đó. Nếu chọn nút gốc, ta chỉ cần cộng thêm vào trạng thái tiếp theo dfn[x] + 1. Kỹ thuật này giúp đưa độ phức tạp xuống O(n*m) bằng cách thao tác tuyến tính trên mảng dFN thay vì gộp đệ quy lồng nhau.