Bài 27.1. Bài toán cái túi 0-1 (Knapsack)
Bài 27.1. Bài toán cái túi 0-1 (Knapsack)
Chào mừng trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng nhau khám phá một bài toán kinh điển trong lĩnh vực tối ưu tổ hợp: Bài toán cái túi 0-1, hay còn gọi là 0-1 Knapsack Problem. Đây không chỉ là một bài toán lý thuyết thú vị mà còn có rất nhiều ứng dụng thực tế.
Hãy tưởng tượng bạn là một nhà thám hiểm đang lạc vào một kho báu cổ kính. Trước mặt bạn là vô số đồ vật giá trị, mỗi thứ có một trọng lượng và giá trị riêng. Tuy nhiên, bạn chỉ mang theo một chiếc túi, và chiếc túi này chỉ có thể chứa được một trọng lượng tối đa nhất định. Nhiệm vụ của bạn là làm thế nào để chọn ra một tập hợp các đồ vật cho vào túi sao cho tổng giá trị thu được là lớn nhất, mà tổng trọng lượng của chúng không vượt quá sức chứa của túi.
Điều đặc biệt ở đây là tính chất "0-1": đối với mỗi đồ vật, bạn chỉ có hai lựa chọn: hoặc là lấy toàn bộ nó cho vào túi (tương ứng với "1"), hoặc là không lấy gì cả (tương ứng với "0"). Bạn không thể xé lẻ hay chỉ lấy một phần của đồ vật.
Nghe có vẻ đơn giản, nhưng bài toán này lại ẩn chứa những thách thức không nhỏ!
Tại sao Bài toán Knapsack 0-1 lại "Khó"?
Thử nghĩ xem làm thế nào để giải quyết bài toán này một cách "ngây thơ" nhất (brute force)? Bạn có thể thử mọi khả năng lựa chọn các đồ vật. Nếu có n đồ vật, thì sẽ có $2^n$ tập hợp con các đồ vật có thể chọn (mỗi đồ vật có 2 trạng thái: được chọn hoặc không được chọn). Đối với mỗi tập hợp con này, bạn kiểm tra xem tổng trọng lượng có vượt quá giới hạn của túi không. Nếu không, bạn tính tổng giá trị và lưu lại nếu nó là giá trị lớn nhất từ trước đến nay.
Cách tiếp cận này chắc chắn sẽ cho ra kết quả đúng, nhưng nó có một nhược điểm cực kỳ nghiêm trọng: số lượng tập hợp con $2^n$ tăng lên rất nhanh khi n lớn. Chỉ với n = 30, $2^{30}$ đã là hơn 1 tỷ. Đối với các bài toán thực tế với hàng trăm, hàng nghìn đồ vật, cách này là hoàn toàn không khả thi về mặt thời gian tính toán.
Vậy làm thế nào để tìm ra lời giải tối ưu mà không phải thử hết tất cả các khả năng? Đây chính là lúc các kỹ thuật giải thuật mạnh mẽ phát huy tác dụng!
Tiếp cận bằng "Tham lam" (Greedy) - Liệu có hiệu quả?
Một ý tưởng ban đầu có thể xuất hiện là sử dụng phương pháp "tham lam" (greedy). Có vài chiến lược tham lam phổ biến:
- Lấy đồ vật có giá trị cao nhất trước: Sắp xếp các đồ vật theo thứ tự giảm dần của giá trị. Lần lượt lấy các đồ vật vào túi nếu túi còn chỗ.
- Lấy đồ vật có trọng lượng nhẹ nhất trước: Sắp xếp các đồ vật theo thứ tự tăng dần của trọng lượng. Lần lượt lấy các đồ vật vào túi nếu túi còn chỗ.
- Lấy đồ vật có tỉ lệ giá trị/trọng lượng cao nhất trước: Sắp xếp các đồ vật theo tỉ lệ giá trị/trọng lượng giảm dần. Lần lượt lấy các đồ vật vào túi nếu túi còn chỗ.
Hãy thử một ví dụ đơn giản để xem các chiến lược tham lam này có tối ưu không nhé:
- Sức chứa túi:
W = 10 - Các đồ vật:
- Vật 1: trọng lượng
w1 = 7, giá trịv1 = 10 - Vật 2: trọng lượng
w2 = 3, giá trịv2 = 4 - Vật 3: trọng lượng
w3 = 4, giá trịv3 = 5
- Vật 1: trọng lượng
Kiểm tra các chiến lược tham lam:
- Giá trị cao nhất: Vật 1 (v=10, w=7), Vật 3 (v=5, w=4), Vật 2 (v=4, w=3).
- Lấy Vật 1: Túi còn 10-7=3 chỗ. Tổng giá trị = 10.
- Xem xét Vật 3: w=4 > 3, không lấy được.
- Xem xét Vật 2: w=3 <= 3, lấy được. Túi còn 3-3=0 chỗ. Tổng giá trị = 10 + 4 = 14.
- Kết quả tham lam 1: Tổng giá trị = 14.
- Trọng lượng nhẹ nhất: Vật 2 (w=3, v=4), Vật 3 (w=4, v=5), Vật 1 (w=7, v=10).
- Lấy Vật 2: Túi còn 10-3=7 chỗ. Tổng giá trị = 4.
- Lấy Vật 3: w=4 <= 7, lấy được. Túi còn 7-4=3 chỗ. Tổng giá trị = 4 + 5 = 9.
- Xem xét Vật 1: w=7 > 3, không lấy được.
- Kết quả tham lam 2: Tổng giá trị = 9.
- Tỉ lệ giá trị/trọng lượng:
- Vật 1: 10/7 ≈ 1.43
- Vật 2: 4/3 ≈ 1.33
- Vật 3: 5/4 = 1.25
- Thứ tự: Vật 1 (10/7), Vật 2 (4/3), Vật 3 (5/4).
- Lấy Vật 1: Túi còn 10-7=3 chỗ. Tổng giá trị = 10.
- Xem xét Vật 2: w=3 <= 3, lấy được. Túi còn 3-3=0 chỗ. Tổng giá trị = 10 + 4 = 14.
- Xem xét Vật 3: w=4 > 0, không lấy được.
- Kết quả tham lam 3: Tổng giá trị = 14.
Bây giờ, hãy thử tổ hợp Vật 2 và Vật 3: Tổng trọng lượng = 3 + 4 = 7 <= 10 (thoả mãn). Tổng giá trị = 4 + 5 = 9. Không phải kết quả tốt nhất.
Thử tổ hợp Vật 1 và Vật 2: Tổng trọng lượng = 7 + 3 = 10 <= 10 (thoả mãn). Tổng giá trị = 10 + 4 = 14.
Thử tổ hợp Vật 1 và Vật 3: Tổng trọng lượng = 7 + 4 = 11 > 10 (không thoả mãn).
Thử tổ hợp chỉ Vật 1: Tổng trọng lượng = 7 <= 10. Tổng giá trị = 10.
Thử tổ hợp chỉ Vật 2: Tổng trọng lượng = 3 <= 10. Tổng giá trị = 4.
Thử tổ hợp chỉ Vật 3: Tổng trọng lượng = 4 <= 10. Tổng giá trị = 5.
Thử tổ hợp cả 3: Tổng trọng lượng = 7+3+4 = 14 > 10 (không thoả mãn).
Các kết quả có thể: 0 (không lấy gì), 10 (Vật 1), 4 (Vật 2), 5 (Vật 3), 9 (Vật 2+3), 14 (Vật 1+2).
Rõ ràng, giá trị tối ưu là 14, đạt được khi chọn Vật 1 và Vật 2.
Trong ví dụ này, chiến lược tham lam theo giá trị cao nhất và tỉ lệ giá trị/trọng lượng cao nhất đều ngẫu nhiên cho ra kết quả đúng. Nhưng đây chỉ là một ví dụ nhỏ. Hãy xét một ví dụ khác:
- Sức chứa túi:
W = 6 - Các đồ vật:
- Vật 1: trọng lượng
w1 = 5, giá trịv1 = 10 - Vật 2: trọng lượng
w2 = 3, giá trịv2 = 6 - Vật 3: trọng lượng
w3 = 3, giá trịv3 = 6
- Vật 1: trọng lượng
Chiến lược tham lam theo tỉ lệ giá trị/trọng lượng:
- Vật 1: 10/5 = 2
- Vật 2: 6/3 = 2
- Vật 3: 6/3 = 2 (Tỉ lệ bằng nhau, giả sử xét theo thứ tự 1, 2, 3)
- Lấy Vật 1 (w=5, v=10): Túi còn 6-5=1 chỗ. Tổng giá trị = 10.
- Xem xét Vật 2 (w=3, v=6): w=3 > 1, không lấy được.
- Xem xét Vật 3 (w=3, v=6): w=3 > 1, không lấy được.
- Kết quả tham lam: Tổng giá trị = 10.
Bây giờ, hãy thử tổ hợp Vật 2 và Vật 3: Tổng trọng lượng = 3 + 3 = 6 <= 6 (thoả mãn). Tổng giá trị = 6 + 6 = 12.
Rõ ràng, giá trị tối ưu là 12, đạt được khi chọn Vật 2 và Vật 3. Chiến lược tham lam theo tỉ lệ giá trị/trọng lượng đã không cho ra kết quả tối ưu trong trường hợp này.
Điều này cho thấy các chiến lược tham lam không đảm bảo tính tối ưu cho Bài toán cái túi 0-1. Chúng ta cần một phương pháp có hệ thống hơn, và đó chính là Quy hoạch động (Dynamic Programming).
Giải pháp bằng Quy hoạch động (Dynamic Programming)
Ý tưởng cốt lõi của Quy hoạch động là chia bài toán lớn thành các bài toán con nhỏ hơn, giải quyết chúng và lưu trữ kết quả để sử dụng lại khi cần. Đối với bài toán Knapsack 0-1, chúng ta có thể định nghĩa các bài toán con như sau:
Gọi dp[i][w] là giá trị lớn nhất có thể thu được khi chỉ xét đến i đồ vật đầu tiên và có sức chứa túi là w.
Chúng ta muốn tính dp[n][W], trong đó n là tổng số đồ vật và W là sức chứa tối đa của túi.
Bây giờ, hãy xem xét cách tính dp[i][w] dựa trên các bài toán con nhỏ hơn. Khi xét đến đồ vật thứ i (với trọng lượng weight[i] và giá trị value[i]) và sức chứa túi hiện tại là w, chúng ta có hai khả năng đối với đồ vật thứ i:
- Không chọn đồ vật thứ
i: Trong trường hợp này, giá trị lớn nhất thu được chính là giá trị lớn nhất khi chỉ xét đếni-1đồ vật đầu tiên với sức chứaw. Tức làdp[i-1][w]. - Chọn đồ vật thứ
i: Khả năng này chỉ xảy ra nếu sức chứawđủ lớn để chứa đồ vật thứi(tức làw >= weight[i]). Nếu chọn đồ vật thứi, chúng ta sẽ nhận được giá trịvalue[i], và bài toán con trở thành: tìm giá trị lớn nhất khi xéti-1đồ vật đầu tiên với sức chứa còn lại làw - weight[i]. Giá trị này làdp[i-1][w - weight[i]]. Tổng giá trị thu được trong trường hợp này làvalue[i] + dp[i-1][w - weight[i]].
Vì chúng ta muốn đạt được giá trị lớn nhất, dp[i][w] sẽ là giá trị lớn hơn trong hai khả năng trên (nếu khả năng 2 có thể xảy ra):
- Nếu
w < weight[i](túi không đủ chỗ cho đồ vật thứi):dp[i][w] = dp[i-1][w](Chỉ có lựa chọn 1: không chọn đồ vậti) - Nếu
w >= weight[i](túi đủ chỗ cho đồ vật thứi):dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]])(Chọn cái nào tốt hơn giữa không chọn và có chọn đồ vậti)
Đây chính là quan hệ truy hồi (recurrence relation) cho bài toán.
Trường hợp cơ sở (Base Cases):
- Khi không có đồ vật nào được xét (
i = 0), với bất kỳ sức chứaw, giá trị lớn nhất là 0.dp[0][w] = 0cho mọiw >= 0. - Khi sức chứa túi là 0 (
w = 0), với bất kỳ số lượng đồ vậti, giá trị lớn nhất là 0 (vì không thể bỏ gì vào túi rỗng).dp[i][0] = 0cho mọii >= 0.
Chúng ta có thể xây dựng một bảng (thường là mảng 2D) dp có kích thước (n+1) x (W+1) để lưu trữ các giá trị dp[i][w] và điền vào bảng này theo thứ tự.
- Các hàng của bảng tương ứng với số lượng đồ vật được xét (từ 0 đến
n). - Các cột của bảng tương ứng với sức chứa túi (từ 0 đến
W).
Bảng được điền từ trên xuống (tăng i) và từ trái sang phải (tăng w).
Kết quả cuối cùng của bài toán sẽ nằm ở ô dp[n][W].
Ví dụ minh hoạ với Quy hoạch động
Sử dụng lại ví dụ thứ hai:
- Sức chứa túi:
W = 6 - Các đồ vật (có thể dùng mảng 0-based hoặc 1-based, ở đây dùng 1-based cho dễ theo dõi bảng DP):
- Vật 1: w=5, v=10
- Vật 2: w=3, v=6
- Vật 3: w=3, v=6
- Số lượng đồ vật
n = 3.
Bảng DP dp[i][w] có kích thước (3+1) x (6+1) = 4 x 7.
Khởi tạo hàng 0 và cột 0 bằng 0:
| i\w | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | ||||||
| 2 | 0 | ||||||
| 3 | 0 |
Điền bảng theo công thức: dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]]) nếu w >= weight[i], ngược lại dp[i][w] = dp[i-1][w].
Xét đồ vật 1 (w=5, v=10):
i = 1weight[1] = 5,value[1] = 10- Điền hàng 1:
w = 0..4:w < weight[1].dp[1][w] = dp[0][w] = 0.w = 5:w >= weight[1].dp[1][5] = max(dp[0][5], value[1] + dp[0][5 - 5]) = max(0, 10 + dp[0][0]) = max(0, 10 + 0) = 10.w = 6:w >= weight[1].dp[1][6] = max(dp[0][6], value[1] + dp[0][6 - 5]) = max(0, 10 + dp[0][1]) = max(0, 10 + 0) = 10.
Bảng sau khi điền hàng 1:
| i\w | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 10 | 10 |
| 2 | 0 | ||||||
| 3 | 0 |
Xét đồ vật 2 (w=3, v=6):
i = 2weight[2] = 3,value[2] = 6- Điền hàng 2:
w = 0..2:w < weight[2].dp[2][w] = dp[1][w].w = 3:w >= weight[2].dp[2][3] = max(dp[1][3], value[2] + dp[1][3 - 3]) = max(0, 6 + dp[1][0]) = max(0, 6 + 0) = 6.w = 4:w >= weight[2].dp[2][4] = max(dp[1][4], value[2] + dp[1][4 - 3]) = max(0, 6 + dp[1][1]) = max(0, 6 + 0) = 6.w = 5:w >= weight[2].dp[2][5] = max(dp[1][5], value[2] + dp[1][5 - 3]) = max(10, 6 + dp[1][2]) = max(10, 6 + 0) = 10.w = 6:w >= weight[2].dp[2][6] = max(dp[1][6], value[2] + dp[1][6 - 3]) = max(10, 6 + dp[1][3]) = max(10, 6 + 0) = 10.
Bảng sau khi điền hàng 2:
| i\w | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 10 | 10 |
| 2 | 0 | 0 | 0 | 6 | 6 | 10 | 10 |
| 3 | 0 |
Xét đồ vật 3 (w=3, v=6):
i = 3weight[3] = 3,value[3] = 6- Điền hàng 3:
w = 0..2:w < weight[3].dp[3][w] = dp[2][w].w = 3:w >= weight[3].dp[3][3] = max(dp[2][3], value[3] + dp[2][3 - 3]) = max(6, 6 + dp[2][0]) = max(6, 6 + 0) = 6.w = 4:w >= weight[3].dp[3][4] = max(dp[2][4], value[3] + dp[2][4 - 3]) = max(6, 6 + dp[2][1]) = max(6, 6 + 0) = 6.w = 5:w >= weight[3].dp[3][5] = max(dp[2][5], value[3] + dp[2][5 - 3]) = max(10, 6 + dp[2][2]) = max(10, 6 + 0) = 10.w = 6:w >= weight[3].dp[3][6] = max(dp[2][6], value[3] + dp[2][6 - 3]) = max(10, 6 + dp[2][3]) = max(10, 6 + 6) = **12**.
Bảng cuối cùng:
| i\w | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 10 | 10 |
| 2 | 0 | 0 | 0 | 6 | 6 | 10 | 10 |
| 3 | 0 | 0 | 0 | 6 | 6 | 10 | 12 |
Kết quả cuối cùng là dp[3][6] = 12, khớp với kết quả tối ưu mà chúng ta đã tìm thủ công trước đó.
Cài đặt C++ cho DP 2D
Đây là cách cài đặt giải pháp DP 2D cho Bài toán cái túi 0-1 bằng C++:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Hàm giải bài toán Knapsack 0-1 bằng Quy hoạch động 2D
int knapsack_dp_2d(int W, const vector<int>& weights, const vector<int>& values) {
int n = weights.size(); // Số lượng đồ vật
// Tạo bảng DP có kích thước (n+1) x (W+1)
// dp[i][w] sẽ lưu giá trị lớn nhất khi xét i đồ vật đầu tiên với sức chứa w
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
// Xây dựng bảng dp
// Duyệt qua từng đồ vật (từ đồ vật thứ 1 đến thứ n)
for (int i = 1; i <= n; ++i) {
// Trọng lượng và giá trị của đồ vật hiện tại (chỉ số i-1 trong mảng gốc)
int current_weight = weights[i - 1];
int current_value = values[i - 1];
// Duyệt qua từng mức sức chứa (từ 0 đến W)
for (int w = 0; w <= W; ++w) {
// Trường hợp 1: Không chọn đồ vật thứ i
// Giá trị lớn nhất không đổi, bằng giá trị khi chỉ xét i-1 đồ vật
dp[i][w] = dp[i - 1][w];
// Trường hợp 2: Có thể chọn đồ vật thứ i (nếu sức chứa đủ)
if (w >= current_weight) {
// So sánh với việc chọn đồ vật thứ i
// Giá trị mới = giá trị của đồ vật i + giá trị lớn nhất khi xét i-1 đồ vật
// với sức chứa còn lại (w - current_weight)
dp[i][w] = max(dp[i][w], current_value + dp[i - 1][w - current_weight]);
}
}
}
// Kết quả cuối cùng nằm ở ô dp[n][W]
return dp[n][W];
}
int main() {
// Ví dụ 1
vector<int> weights1 = {10, 20, 30};
vector<int> values1 = {60, 100, 120};
int W1 = 50;
int max_value1 = knapsack_dp_2d(W1, weights1, values1);
cout << "Vi du 1:" << endl;
cout << "Cac do vat (trong luong, gia tri): {(10, 60), (20, 100), (30, 120)}" << endl;
cout << "Suc chua tui: " << W1 << endl;
cout << "Gia tri lon nhat co the thu duoc: " << max_value1 << endl; // Output: 220 (chon vat 10 va 20)
cout << "--------------------" << endl;
// Ví dụ 2 (ví dụ đã phân tích ở trên)
vector<int> weights2 = {5, 3, 3};
vector<int> values2 = {10, 6, 6};
int W2 = 6;
int max_value2 = knapsack_dp_2d(W2, weights2, values2);
cout << "Vi du 2:" << endl;
cout << "Cac do vat (trong luong, gia tri): {(5, 10), (3, 6), (3, 6)}" << endl;
cout << "Suc chua tui: " << W2 << endl;
cout << "Gia tri lon nhat co the thu duoc: " << max_value2 << endl; // Output: 12 (chon 2 vat 3)
return 0;
}
Giải thích mã C++ (DP 2D):
- Chúng ta khai báo hàm
knapsack_dp_2dnhận vào sức chứaW, vector trọng lượngweightsvà vector giá trịvalues. - Biến
nlưu trữ số lượng đồ vật. - Tạo một
vector<vector<int>>có têndpvới kích thước(n+1) x (W+1)và khởi tạo tất cả các giá trị bằng 0. Hàng 0 và cột 0 tự động được khởi tạo đúng với trường hợp cơ sở. - Vòng lặp ngoài
for (int i = 1; i <= n; ++i)duyệt qua từng đồ vật, từ đồ vật thứ 1 đến thứn. Lưu ý: chỉ sốitrong DP table tương ứng với đồ vật thứi(1-based), nên khi truy cậpweightsvàvalues(0-based) ta dùngi-1. - Vòng lặp trong
for (int w = 0; w <= W; ++w)duyệt qua từng mức sức chứa có thể có, từ 0 đếnW. - Bên trong vòng lặp, chúng ta thực hiện logic của quan hệ truy hồi:
dp[i][w] = dp[i - 1][w];: Mặc định gán giá trị lớn nhất là khi không chọn đồ vật thứi(giá trị này đã được tính ở hàngi-1).if (w >= current_weight): Kiểm tra xem sức chứawcó đủ để chứa đồ vật thứikhông.dp[i][w] = max(dp[i][w], current_value + dp[i - 1][w - current_weight]);: Nếu đủ, so sánh giá trị hiện tạidp[i][w](không chọn đồ vật i) với giá trị khi chọn đồ vật i (current_value+ giá trị tối ưu choi-1đồ vật với sức chứa còn lạiw - current_weight). Cập nhậtdp[i][w]bằng giá trị lớn hơn trong hai trường hợp.
- Sau khi điền đầy đủ bảng,
dp[n][W]chứa giá trị lớn nhất có thể thu được khi xét tất cảnđồ vật với sức chứaW.
Độ phức tạp thời gian của giải pháp DP 2D này là O(n*W) vì chúng ta điền vào một bảng có kích thước (n+1) x (W+1).
Độ phức tạp không gian là O(n*W) để lưu trữ bảng DP.
Đối với nhiều bài toán, sức chứa W có thể rất lớn, trong khi số lượng đồ vật n lại nhỏ hơn. Trong trường hợp đó, độ phức tạp O(nW) có thể trở nên không hiệu quả. Tuy nhiên, đối với bài toán Knapsack 0-1, nếu W không quá lớn so với n, DP là một giải pháp hiệu quả hơn nhiều so với O(2^n). Do W là một giá trị, không phải kích thước input theo nghĩa bit, nên O(nW) được gọi là độ phức tạp pseudo-polynomial.
Tối ưu không gian (Space Optimization)
Bạn có nhận thấy điều gì đặc biệt trong quan hệ truy hồi dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]]) không? Để tính giá trị cho hàng i, chúng ta chỉ cần các giá trị từ hàng i-1. Điều này gợi ý rằng chúng ta có thể giảm bớt không gian lưu trữ. Thay vì lưu toàn bộ bảng 2D, chúng ta chỉ cần lưu trữ thông tin của hai hàng: hàng hiện tại đang tính và hàng trước đó.
Thực tế, chúng ta có thể tối ưu không gian mạnh mẽ hơn nữa, chỉ cần một mảng 1D kích thước W+1. Mảng này, gọi là dp[w], sẽ lưu trữ giá trị lớn nhất có thể thu được với sức chứa w khi xét đến tập hợp các đồ vật đã được xử lý cho đến thời điểm hiện tại.
Khi xét đến đồ vật thứ i (với trọng lượng current_weight và giá trị current_value), chúng ta muốn cập nhật mảng dp dựa trên các giá trị trước khi xét đồ vật i. Cụ thể, để tính giá trị tối ưu cho sức chứa w sau khi xét đồ vật i, chúng ta so sánh:
- Giá trị tối ưu cho sức chứa
wtrước khi xét đồ vậti(tương ứng vớidp[i-1][w]trong công thức 2D). Giá trị này hiện đang được lưu trongdp[w]của mảng 1D. - Giá trị khi chọn đồ vật thứ
i:current_value+ giá trị tối ưu cho sức chứaw - current_weighttrước khi xét đồ vậti(tương ứng vớivalue[i] + dp[i-1][w - weight[i]]trong công thức 2D). Giá trị này tương ứng vớicurrent_value + dp[w - current_weight]của mảng 1D, nhưng điều quan trọng làdp[w - current_weight]phải là giá trị khi chưa xét đồ vậti.
Để đảm bảo dp[w - current_weight] chưa bị cập nhật bởi đồ vật thứ i, chúng ta cần duyệt mức sức chứa w từ W giảm dần về weight[i]. Nếu duyệt từ 0 tăng dần, khi tính dp[w], giá trị dp[w - current_weight] có thể đã bị cập nhật bởi chính đồ vật i, dẫn đến kết quả sai (nó sẽ giống bài toán Knapsack không giới hạn số lượng).
Quan hệ truy hồi cho DP 1D:
dp[w] = max(dp[w], value[i] + dp[w - weight[i]]) for w từ W xuống đến weight[i].
Các giá trị dp[w] với w < weight[i] không thay đổi khi xét đồ vật thứ i.
Mảng DP 1D: dp[0...W], kích thước W+1. Khởi tạo tất cả bằng 0.
Cài đặt C++ cho DP 1D (Tối ưu không gian)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Hàm giải bài toán Knapsack 0-1 bằng Quy hoạch động 1D (tối ưu không gian)
int knapsack_dp_1d(int W, const vector<int>& weights, const vector<int>& values) {
int n = weights.size(); // Số lượng đồ vật
// Tạo mảng DP 1D có kích thước W+1
// dp[w] sẽ lưu giá trị lớn nhất khi xét các đồ vật đã qua
// với sức chứa tối đa w
vector<int> dp(W + 1, 0);
// Duyệt qua từng đồ vật (từ đồ vật 0 đến n-1)
for (int i = 0; i < n; ++i) {
int current_weight = weights[i];
int current_value = values[i];
// Duyệt qua mức sức chứa TỪ LỚN XUỐNG NHỎ
// Chỉ xét các mức sức chứa đủ lớn để chứa đồ vật hiện tại
for (int w = W; w >= current_weight; --w) {
// dp[w] (cũ): giá trị lớn nhất với sức chứa w khi chưa xét đồ vật i
// current_value + dp[w - current_weight] (cũ): giá trị khi chọn đồ vật i
// (lấy giá trị của i + giá trị tối ưu cho sức chứa còn lại w - current_weight
// khi chưa xét đồ vật i)
dp[w] = max(dp[w], current_value + dp[w - current_weight]);
}
// Các w < current_weight: dp[w] giữ nguyên giá trị từ bước trước
}
// Kết quả cuối cùng nằm ở dp[W]
return dp[W];
}
int main() {
// Ví dụ 1
vector<int> weights1 = {10, 20, 30};
vector<int> values1 = {60, 100, 120};
int W1 = 50;
int max_value1 = knapsack_dp_1d(W1, weights1, values1);
cout << "Vi du 1 (toi uu khong gian):" << endl;
cout << "Cac do vat (trong luong, gia tri): {(10, 60), (20, 100), (30, 120)}" << endl;
cout << "Suc chua tui: " << W1 << endl;
cout << "Gia tri lon nhat co the thu duoc: " << max_value1 << endl; // Output: 220
cout << "--------------------" << endl;
// Ví dụ 2
vector<int> weights2 = {5, 3, 3};
vector<int> values2 = {10, 6, 6};
int W2 = 6;
int max_value2 = knapsack_dp_1d(W2, weights2, values2);
cout << "Vi du 2 (toi uu khong gian):" << endl;
cout << "Cac do vat (trong luong, gia tri): {(5, 10), (3, 6), (3, 6)}" << endl;
cout << "Suc chua tui: " << W2 << endl;
cout << "Gia tri lon nhat co the thu duoc: " << max_value2 << endl; // Output: 12
return 0;
}
Giải thích mã C++ (DP 1D):
- Hàm
knapsack_dp_1dtương tự như bản 2D, chỉ khác ở việc sử dụng mảng DP. - Tạo một
vector<int>có têndpvới kích thướcW+1và khởi tạo tất cả bằng 0. - Vòng lặp ngoài
for (int i = 0; i < n; ++i)duyệt qua từng đồ vật (lần này dùng 0-based index cho tiện truy cậpweightsvàvalues). - Vòng lặp trong
for (int w = W; w >= current_weight; --w)duyệt qua mức sức chứa từWxuống đếncurrent_weight. Đây là điểm mấu chốt của việc tối ưu không gian. Chúng ta chỉ cần xét các mức sức chứa đủ lớn để có thể chứa đồ vật hiện tại (w >= current_weight). - Bên trong vòng lặp, cập nhật
dp[w]bằng giá trị lớn nhất giữa:dp[w]hiện tại: Đây là giá trị tối ưu cho sức chứawkhi chưa xét đồ vật thứi. Tương ứng với trường hợp không chọn đồ vậti.current_value + dp[w - current_weight]: Đây là giá trị khi chọn đồ vật thứi.dp[w - current_weight]là giá trị tối ưu cho sức chứaw - current_weight. Vì chúng ta duyệtwgiảm dần, khi tínhdp[w], giá trịdp[w - current_weight]vẫn là giá trị từ bước trước (trước khi xét đồ vậti), chưa bị cập nhật bởi đồ vậti. Điều này đảm bảo mỗi đồ vật chỉ được xét chọn một lần cho mỗi đường đi đến sức chứaw.
- Kết quả cuối cùng vẫn nằm ở
dp[W].
Độ phức tạp thời gian của giải pháp DP 1D này vẫn là O(n*W).
Tuy nhiên, độ phức tạp không gian đã giảm xuống còn O(W), đây là một cải tiến đáng kể nếu n rất lớn so với W.
Bài tập ví dụ:
Hai tập hợp II
Trong một buổi làm việc, lãnh đạo cấp trên đã đưa cho FullHouse Dev một bài toán thú vị về tập hợp. V
Bài toán
FullHouse Dev cần đếm số cách để chia các số từ \(1\) đến \(n\) thành hai tập hợp có tổng bằng nhau. Ví dụ với \(n = 7\), có bốn cách chia như sau:
- {1,3,4,6} và {2,5,7}
- {1,2,5,6} và {3,4,7}
- {1,2,4,7} và {3,5,6}
- {1,6,7} và {2,3,4,5}
INPUT FORMAT:
- Dòng duy nhất chứa một số nguyên \(n\).
OUTPUT FORMAT:
- In ra số cách chia có thể theo modulo \(10^9+7\).
Ràng buộc:
- \(1 \leq n \leq 500\)
Ví dụ
INPUT
7OUTPUT
4Giải thích
Với \(n = 7\), có đúng 4 cách chia các số từ 1 đến 7 thành hai tập hợp có tổng bằng nhau như đã liệt kê trong phần mô tả bài toán. Bài toán yêu cầu đếm số cách chia tập hợp ${1, 2, \dots, n}$ thành hai tập hợp con không giao nhau có tổng bằng nhau.
Điều kiện cần: Tổng của tất cả các số từ 1 đến $n$ là $S = \frac{n(n+1)}{2}$. Nếu tập hợp được chia thành hai tập con có tổng bằng nhau, gọi tổng của mỗi tập con là $T$, thì $2T = S$. Do đó, $S$ phải là một số chẵn. Nếu $S$ lẻ, không thể chia thành hai tập có tổng bằng nhau, số cách chia là 0.
Biến đổi bài toán: Nếu $S$ chẵn, mỗi tập con phải có tổng là $T = S/2$. Bài toán trở thành: đếm số cách chọn một tập con từ ${1, 2, \dots, n}$ sao cho tổng các phần tử của tập con đó bằng $T$. Nếu ta chọn được một tập con có tổng $T$, thì các phần tử còn lại sẽ tạo thành tập con thứ hai, và tổng của chúng tự động là $S - T = S - S/2 = T$.
Quan hệ giữa số cách chọn tập con và số cách chia: Mỗi cách chọn một tập con có tổng $T$ (gọi là tập A) tương ứng với một cách chia thành hai tập {A, ${1, \dots, n} \setminus A$}. Vì tập A và tập ${1, \dots, n} \setminus A$ là khác nhau (vì chúng không giao nhau và hợp lại là ${1, \dots, n}$), mỗi cách chia {tập 1, tập 2} sẽ được đếm hai lần khi ta đếm số cách chọn một tập con có tổng $T$ (một lần khi chọn tập 1, một lần khi chọn tập 2). Do đó, số cách chia chính là một nửa số cách chọn tập con có tổng $T$.
Sử dụng Quy hoạch động (Dynamic Programming): Đây là bài toán đếm số cách tạo ra một tổng nhất định từ một tập các vật phẩm với trọng lượng và giá trị bằng nhau (ở đây trọng lượng = giá trị = số đó). Ta có thể dùng DP.
- Định nghĩa trạng thái: Gọi $dp[j]$ là số cách để tạo ra tổng $j$ sử dụng các số từ 1 đến $i$ (khi ta đang xử lý số $i$).
- Khởi tạo: $dp[0] = 1$ (một cách để có tổng 0 là không chọn số nào), $dp[j] = 0$ cho $j > 0$.
- Công thức truy hồi: Duyệt qua các số $i$ từ 1 đến $n$. Đối với mỗi số $i$, ta cập nhật mảng $dp$. Để có tổng $j$ sử dụng số $i$, ta phải có tổng $j-i$ trước đó (không dùng số $i$). Do đó, số cách để có tổng $j$ sau khi xét số $i$ sẽ tăng thêm số cách có tổng $j-i$ trước khi xét số $i$. $dp[j] = dp[j] + dp[j-i]$.
- Để tránh sử dụng số $i$ nhiều lần hoặc sử dụng giá trị $dp[j-i]$ đã được cập nhật bởi chính số $i$, ta cần duyệt tổng $j$ từ lớn xuống nhỏ (từ $T$ về đến $i$).
- $dp[j] = (dp[j] + dp[j-i]) \pmod{10^9+7}$ cho $j$ từ $T$ xuống đến $i$.
- Sau khi duyệt hết $i$ từ 1 đến $n$, $dp[T]$ sẽ là tổng số cách chọn một tập con có tổng bằng $T$.
Kết quả cuối cùng: Số cách chia là $dp[T] / 2$. Vì ta cần kết quả modulo $10^9+7$, phép chia cho 2 tương đương với nhân với nghịch đảo modulo của 2 theo modulo $10^9+7$. Nghịch đảo modulo của 2 là $(10^9+7+1)/2$.
- Số cách chia = $(dp[T] \times ((10^9+7 + 1) / 2)) \pmod{10^9+7}$.
Tóm tắt hướng giải:
- Tính tổng $S = n(n+1)/2$.
- Nếu $S$ lẻ, kết quả là 0.
- Nếu $S$ chẵn, tính tổng mục tiêu $T = S/2$.
- Sử dụng Quy hoạch động 1D: $dp[j]$ là số cách tạo tổng $j$. Khởi tạo $dp[0]=1$, các $dp[j>0]=0$.
- Duyệt $i$ từ 1 đến $n$. Với mỗi $i$, duyệt $j$ từ $T$ xuống đến $i$: $dp[j] = (dp[j] + dp[j-i]) \pmod{10^9+7}$.
- Kết quả DP $dp[T]$ là số cách chọn một tập con có tổng $T$.
- Số cách chia là $(dp[T] \times ((10^9+7 + 1) / 2)) \pmod{10^9+7}$.
Làm thêm nhiều bài tập miễn phí tại đây
Khóa học liên quan
Giảm giá!
Comments