Chuyên Đề Quy Hoạch Động Cái Túi - DP KNAPSACK

# Chuyên Đề Quy Hoạch Động Cái Túi - DP KNAPSACK * [Kiến Thức Cần Biết](#Kiến-Thức-Cần-Biết) * [Giới Thiệu](#Giới-Thiệu) * [Ứng Dụng Thực Tiễn Của Bài Toán Cái Túi](#Ứng-Dụng-Thực-Tiễn-Của-Bài-Toán-Cái-Túi) * [Các Dạng Quy Hoạch Động Cái Túi](#Các-Dạng-Quy-Hoạch-Động-Cái-Túi) * [Tổng Quát Về Quy Hoạch Động Cái Túi](#Tổng-Quát-Về-Quy-Hoạch-Động-Cái-túi) * [Bài Toán Xếp Ba Lô Bị Chặn (BKP)](#Bài-toán-xếp-ba-lô-bị-chặn-BKP) * [Bài toán xếp ba lô không bị chặn (UKP)](#Bài-toán-xếp-ba-lô-không-bị-chặn-UKP) * [Phát Biểu Bài Toán](#Phát-Biểu-Bài-Toán) * [Ý Tưởng](#Ý-Tưởng) * [Trường Hợp Mỗi Vật Chỉ Được Chọn 1 Lần](#Trường-Hợp-Mỗi-Vật-Chỉ-Được-Chọn-1-Lần) * [Trường Hợp Mỗi Vật Được Chọn Nhiều Lần](#Trường-Hợp-Mỗi-Vật-Được-Chọn-Nhiều-Lần) * [Bảng Phương Án](#Bảng-Phương-Án) * [Trường Hợp Mỗi Vật Chỉ Được Chọn 1 Lần](#Trường-Hợp-Mỗi-Vật-Chỉ-Được-Chọn-1-Lần13) * [Trường Hợp Mỗi Vật Được Chọn Nhiều Lần](#Trường-Hợp-Mỗi-Vật-Được-Chọn-Nhiều-Lần15) * [Truy Vết](#Truy-Vết) * [Trường Hợp Mỗi Vật Chỉ Được Chọn 1 Lần](#Trường-Hợp-Mỗi-Vật-Chỉ-Được-Chọn-1-Lần18) * [Trường Hợp Mỗi Vật Được Chọn Nhiều Lần](#Trường-Hợp-Mỗi-Vật-Được-Chọn-Nhiều-Lần19) * [Cài Đặt](#Cài-Đặt) * [Trường Hợp Mỗi Vật Chỉ Được Chọn 1 Lần](#Trường-Hợp-Mỗi-Vật-Chỉ-Được-Chọn-1-Lần21) * [Trường Hợp Mỗi Vật Được Chọn Nhiều Lần](#Trường-Hợp-Mỗi-Vật-Được-Chọn-Nhiều-Lần22) * [Bài tập áp dụng](#Bài-tập-áp-dụng) * [Tài liệu tham khảo](#Tài-liệu-tham-khảo) ## Kiến Thức Cần Biết **Để đọc hiểu bài viết sau một cách hiệu quả, bạn đọc nên có sẵn các kiến thức về :** * [Nhập môn Quy hoạch động](https://wiki.vnoi.info/translate/topcoder/dynamic-programming) * [Đệ quy và Thuật toán quay lui](https://wiki.vnoi.info/algo/basic/backtracking.md) ## Giới Thiệu Bài toán Cái túi, Bài toán Xếp ba lô, Bài toán Knapsack,… là những tên gọi khác nhau mà chúng ta thường nghe đến, nhưng tất cả đều dùng để chỉ chung một bài toán **tối ưu hóa tổ hợp** --- > Cho một tập hợp các vật phẩm, mỗi vật có trọng lượng và giá trị nhất định, xác định xem nên chọn những vật phẩm nào vào bộ sưu tập sao cho tổng trọng lượng không vượt quá một giới hạn nhất định và tổng giá trị là lớn nhất có thể. --- Nó có tên gọi này từ tình huống mà một người phải đối mặt khi bị giới hạn bởi một cái ba lô **có kích thước** cố định và phải lấp đầy nó bằng những vật phẩm **có giá trị nhất định**. Vấn đề này thường xuất hiện trong phân bổ tài nguyên, nơi các nhà ra quyết định phải chọn từ một tập hợp các dự án hoặc nhiệm vụ không thể chia nhỏ, trong điều kiện ngân sách cố định hoặc ràng buộc thời gian. Bài toán này đã được nghiên cứu trong hơn một thế kỷ với những nghiên cứu đầu tiên có từ năm 1897, và nó là một trong những bài toán có ứng dụng vô cùng to lớn trong thực tế. ![vbjvCeRA](https://hackmd.io/_uploads/rJtTvC5K1l.png) ## Ứng Dụng Thực Tiễn Của Bài Toán Cái Túi Bài toán cái túi xuất hiện trong các quá trình ra quyết định thực tế trong nhiều lĩnh vực khác nhau, chẳng hạn như: - Tìm cách cắt nguyên liệu thô ít lãng phí nhất. - Lựa chọn các khoản đầu tư và danh mục đầu tư. - Lựa chọn tài sản để chứng khoán hóa có tài sản đảm bảo. - Tạo khóa cho hệ mật mã cái túi **Merkle–Hellman** và các hệ mật mã cái túi khác. --- Một ứng dụng sớm của thuật toán cái túi là trong việc **xây dựng và chấm điểm các bài kiểm tra**, trong đó người làm bài có thể lựa chọn câu hỏi để trả lời : - Nếu một bài kiểm tra có **12 câu hỏi**, mỗi câu **10 điểm**, thí sinh chỉ cần trả lời **10 câu** để đạt điểm tối đa **100 điểm**. - Tuy nhiên, nếu điểm phân phối không đều giữa các câu hỏi, việc chọn câu để tối đa hóa điểm số sẽ khó hơn. - **Feuerman và Weiss** đề xuất hệ thống bài kiểm tra với tổng **125 điểm**, học sinh cần chọn câu hỏi sao cho tổng điểm không vượt quá **100** và đạt số điểm tối đa. Sử dụng **thuật toán cái túi**, ta có thể xác định tập hợp câu hỏi giúp mỗi học sinh đạt điểm số cao nhất có thể. --- Một nghiên cứu năm 1999 của Kho lưu trữ Thuật toán Đại học Stony Brook cho thấy rằng, trong số 75 bài toán thuật toán liên quan đến lĩnh vực thuật toán tổ hợp và kỹ thuật thuật toán, bài toán cái túi đứng thứ 19 về mức độ phổ biến và là bài toán cần thiết thứ ba, chỉ sau cây hậu tố và bài toán đóng gói thùng. ## Các Dạng Quy Hoạch Động Cái Túi Có rất nhiều dạng khác nhau của bài toán cái túi nhưng những dạng tiêu biểu của bài toán này có thể kể đến là: - **Bài toán Knapsack với các giá trị số thực**: Trọng lượng và giá trị của các món đồ là số thực. Bài toán này chỉ có thể giải quyết bằng phương pháp Quay lui (hoặc cải tiến bằng Nhánh cận). - **Bài toán Knapsack cho phép cắt nhỏ đồ vật (Fractional Knapsack)**: Các đồ vật được phép cắt ra và lấy một phần. Bài toán này có thể giải quyết bằng phương pháp Tham lam. - **Bài toán cái túi có giới hạn (Bounded Knapsack Problem - BKP)**: Các vật chỉ có thể chọn hoặc không chọn, ngoài ra giá trị và trọng lượng của các vật đều là số nguyên. Bài toán này có thể giải bằng phương pháp Quy hoạch động. - **Bài toán cái túi không giới hạn (Unbounded Knapsack Problem - UKP)** : Có thể đưa vào nhiều bản sao của mỗi vật phẩm, ngoài ra giá trị và trọng lượng của các vật đều là số nguyên. Bài toán này có thể giải bằng phương pháp Quy hoạch động. --- Trong bài viết này, chúng ta sẽ cùng tập trung nghiên cứu **Bài toán cái túi có giới hạn (Bounded Knapsack Problem - BKP)** và **Bài toán cái túi không giới hạn (Unbounded Knapsack Problem - UKP)**. ## Tổng Quát Về Quy Hoạch Động Cái túi Bài toán phổ biến nhất được giải là **bài toán xếp ba lô 0-1**, trong đó số lượng $x_i$ của mỗi loại đồ vật bị giới hạn chỉ có thể là 0 hoặc 1. Cho một tập hợp gồm $n$ đồ vật được đánh số từ 1 đến $n$, mỗi đồ vật có trọng lượng $w_i$ và giá trị $v_i$, cùng với một giới hạn trọng lượng tối đa là $W$: $$ \text{Cực đại hóa} \sum_{i=1}^{n} v_i x_i $$ **Sao cho:** $$ \sum_{i=1}^{n} w_i x_i \leq W, \quad x_i \in \{0, 1\}. $$ Ở đây, $x_i$ đại diện cho số lần xuất hiện của đồ vật $i$ trong ba lô. Mục tiêu là tối đa hóa tổng giá trị của các đồ vật trong ba lô sao cho tổng trọng lượng của chúng không vượt quá khả năng chứa của ba lô. --- ### **Bài toán xếp ba lô bị chặn (BKP)** Loại bỏ ràng buộc rằng mỗi đồ vật chỉ có một lần, nhưng vẫn giới hạn số lượng $x_i$ của mỗi loại đồ vật không vượt quá một giá trị nguyên dương tối đa $c$: $$ \text{Cực đại hóa} \sum_{i=1}^{n} v_i x_i $$ **Sao cho:** $$ \sum_{i=1}^{n} w_i x_i \leq W, \quad x_i \in \{0, 1, 2, \dots, c\}. $$ --- ### **Bài toán xếp ba lô không bị chặn (UKP)** Không giới hạn số lượng của mỗi loại đồ vật, tức là $x_i$ có thể là bất kỳ số nguyên không âm nào: $$ \text{Cực đại hóa} \sum_{i=1}^{n} v_i x_i $$ **Sao cho:** $$ \sum_{i=1}^{n} w_i x_i \leq W, \quad x_i \in \mathbb{N}. $$ Một ví dụ về bài toán xếp ba lô không bị chặn là khi số lượng mỗi cuốn sách trong thư viện không bị giới hạn, và bạn có thể chọn bất kỳ số lượng nào miễn là tổng trọng lượng không vượt quá khả năng chứa của ba lô. ## Phát Biểu Bài Toán **Bài toán xếp ba lô trong siêu thị** Trong siêu thị có $n$ đồ vật ($n \leq 1000$), đồ vật thứ $i$ có trọng lượng là $W[i] \leq 1000$ và giá trị $V[i] \leq 1000$. Một tên trộm đột nhập vào siêu thị, hắn mang theo một cái túi có thể mang được tối đa trọng lượng $M$ ($M \leq 1000$). Hỏi tên trộm sẽ lấy đi những đồ vật nào để được tổng giá trị lớn nhất. **Giải quyết bài toán trong các trường hợp sau:** - Mỗi vật chỉ được chọn một lần. - Mỗi vật được chọn nhiều lần (không hạn chế số lần). **Input Data** - Dòng 1: $n$, $m$ cách nhau ít nhất một dấu cách. - $n$ dòng tiếp theo: Mỗi dòng gồm 2 số $W_i, V_i$, là chi phí và giá trị của đồ vật thứ $i$. **Output Data** - Ghi giá trị lớn nhất tên trộm có thể lấy. ## Ý Tưởng ### **Trường Hợp Mỗi Vật Chỉ Được Chọn 1 Lần** Ta nhận thấy rằng: Giá trị của cái túi phụ thuộc vào hai yếu tố: 1. Có bao nhiêu vật đang được xét. 2. Trọng lượng còn lại của cái túi có thể chứa được. Do vậy, chúng ta có **hai đại lượng biến thiên**, nên để tối ưu, chúng ta sử dụng **bảng phương án** dưới dạng **bảng 2 chiều**. --- **Xây dựng công thức quy hoạch động** Gọi $F[i,j]$ là giá trị lớn nhất của cái túi khi xét từ vật $1$ đến vật $i$ và trong cái túi chưa vượt quá $j$. Với giới hạn $j$, việc chọn tối ưu trong số các vật $\{1,2,...,i-1\}$ có hai khả năng: 1. **Không chọn vật thứ $i$** Khi đó, $F[i,j]$ là giá trị lớn nhất có thể chọn trong số các vật $\{1,2,...,i-1\}$ với giới hạn trọng lượng là $j$, tức là: $$ F[i,j] = F[i-1,j] $$ 2. **Chọn vật thứ $i$** Nếu có chọn vật thứ $i$ (phải thỏa điều kiện $W[i] \leq j$) thì $F[i,j]$ bằng giá trị vật thứ $i$ là $V[i]$ cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các vật $\{1,2,...,i-1\}$ với giới hạn trọng lượng $j - W[i]$, tức là: $$ F[i,j] = V[i] + F[i-1, j-W[i]] $$ Do đó, ta cần **xem xét giữa việc chọn hoặc không chọn vật $i$ để tìm giá trị lớn nhất**, từ đó có công thức **quy hoạch động** như sau: - **Điều kiện cơ sở:** $$ F[0,j] = 0 \quad \text{(hiển nhiên) – Bài toán con nhỏ nhất.} $$ - **Công thức truy hồi:** $$ F[i,j] = \max(F[i-1,j], V[i] + F[i-1, j-W[i]]) $$ --- ### **Trường Hợp Mỗi Vật Được Chọn Nhiều Lần** Tương tự như suy luận ở trên, ta xét: **1. Không chọn vật thứ $i$** Nếu không chọn vật thứ $i$ thì $F[i,j]$ là giá trị lớn nhất có thể chọn trong số các vật $\{1,2,...,i-1\}$ với giới hạn trọng lượng là $j$, tức là: $$ F[i,j] = F[i-1,j] $$ **2. Chọn vật thứ $i$** Nếu có chọn vật thứ $i$ (phải thỏa điều kiện $W[i] \leq j$) thì $F[i,j]$ bằng giá trị vật thứ $i$ là $V[i]$ cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các vật $\{1,2,...,i\}$ với giới hạn trọng lượng $j - W[i]$ (vì vật $i$ vẫn có thể được chọn tiếp), tức là: $$ F[i,j] = V[i] + F[i,j-W[i]] $$ **Công thức truy hồi** Do vậy, chúng ta có công thức **quy hoạch động**: - **Điều kiện cơ sở:** $$ F[0,j] = 0 \quad \text{(hiển nhiên) – Bài toán con nhỏ nhất.} $$ - **Công thức tổng quát:** $$ F[i,j] = \max(F[i-1,j], V[i] + F[i,j-W[i]]) $$ --- ## **Bảng Phương Án** Ta xây dựng bảng phương án dựa trên công thức truy hồi đã trình bày trước đó. Để kiểm tra kết quả có chính xác hay không (nếu không chính xác chúng ta sẽ xây dựng lại hàm mục tiêu). Thông qua cách xây dựng hàm mục tiêu và bảng phương án, chúng ta sẽ hướng việc truy vết. --- ### **Trường Hợp Mỗi Vật Chỉ Được Chọn 1 Lần** **Input** $5$ $15$ $12$ $4$ $2$ $2$ $1$ $1$ $1$ $2$ $4$ $10$ **OUTPUT** $15$ #### **Bảng phương án:** | NM | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |----|----|----|----|----|----|----|----|----|----|----|----|----|----|----|----|----| | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 4 | 4 | | 2 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 6 | 6 | | 3 | 0 | 1 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 4 | 5 | 5 | 7 | 7 | | 4 | 0 | 2 | 3 | 4 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 6 | 7 | 8 | 8 | | 5 | 0 | 2 | 3 | 4 | 10 | 12 | 13 | 14 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 👉 **Kết quả:** Chúng ta có thể chọn vật **2, 3, 4, 5**. --- ### **Trường Hợp Mỗi Vật Được Chọn Nhiều Lần** **Input** $5$ $15$ $12$ $4$ $2$ $2$ $1$ $1$ $1$ $2$ $4$ $10$ **OUTPUT** $36$ #### **Bảng phương án:** | NM | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |----|----|----|----|----|----|----|----|----|----|----|----|----|----|----|----|----| | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 4 | 4 | | 2 | 0 | 0 | 2 | 2 | 4 | 4 | 6 | 6 | 8 | 8 | 10 | 10 | 12 | 12 | 14 | 14 | | 3 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | | 4 | 0 | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 22 | 24 | 26 | 28 | 30 | | 5 | 0 | 2 | 4 | 6 | 10 | 12 | 14 | 16 | 20 | 22 | 24 | 26 | 30 | 32 | 34 | 36 | 👉 **Kết quả:** Chúng ta có thể chọn vật **4 (3 lần)** và vật **5 (3 lần)**. ## **Truy Vết** ### **Trường Hợp Mỗi Vật Chỉ Được Chọn 1 Lần** Trong bảng **phương án**, $F[n,M]$ chính là giá trị lớn nhất thu được khi chọn trong cả $n$ vật với giới hạn trọng lượng là $M$. - Nếu $F[n,M] = F[n-1,M]$, thì tức là **không chọn vật thứ $n$**, ta truy về $F[n-1,M]$. - Còn nếu $F[n,M] \neq F[n-1,M]$, thì ta **chọn vật thứ $n$** và truy vết về $F[n-1,M - W_n]$. --- ### **Trường Hợp Mỗi Vật Được Chọn Nhiều Lần** Trong bảng **phương án**, $F[n,M]$ chính là giá trị lớn nhất thu được khi chọn trong cả $n$ vật với giới hạn trọng lượng là $M$. - Nếu $F[n,M] = F[n-1,M]$, thì tức là **không chọn vật thứ $n$**, ta truy về $F[n-1,M]$. - Còn nếu $F[n,M] \neq F[n-1,M]$, thì ta **chọn vật thứ $n$** và truy vết về $F[n,M - W_n]$. ## Cài Đặt ### Trường Hợp Mỗi Vật Chỉ Được Chọn 1 Lần ```cpp #include <bits/stdc++.h> using namespace std; int main() { // Tăng tốc độ nhập xuất trong C++: ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // Mở file input/output freopen("VALIA.INP","r",stdin); freopen("VALIA.OUT","w",stdout); long long n, m; // Đọc n (số vật phẩm) và m (sức chứa của túi) cin >> n >> m; // Mảng a[] lưu trọng lượng (weight), b[] lưu giá trị (value) của vật phẩm long long a[n+1], b[n+1]; for (long long i = 1; i <= n; i++) { cin >> a[i] >> b[i]; } // Tạo mảng dp 2 chiều: // dp[i][j] = giá trị tối đa khi xét đến vật phẩm thứ i với sức chứa j static long long dp[10001][10001]; // hoặc dùng dp[n+1][m+1], nhưng cần cẩn thận giới hạn bộ nhớ // Khởi tạo dp với 0 (khi i=0 hoặc j=0, giá trị đều là 0) for (long long i = 0; i <= n; i++) { for (long long j = 0; j <= m; j++) { dp[i][j] = 0; } } // Duyệt qua từng vật phẩm i for (long long i = 1; i <= n; i++) { // Duyệt qua các mức sức chứa j for (long long j = 1; j <= m; j++) { // Ban đầu, giả sử không chọn vật phẩm i dp[i][j] = dp[i-1][j]; // Nếu có thể chọn vật phẩm i (vì a[i] <= j), // kiểm tra xem chọn vật phẩm i có tăng giá trị tốt hơn không if (j >= a[i]) { dp[i][j] = max(dp[i][j], dp[i-1][j - a[i]] + b[i]); } } } // Kết quả cuối cùng nằm tại dp[n][m] cout << dp[n][m]; return 0; } ``` **Độ phức tạp** - **Thời gian**: $O(n * m)$, vì với mỗi trong $n$ vật phẩm, ta duyệt qua $m$ sức chứa. - **Không gian**: $O(n * m)$, do lưu một mảng 2 chiều `dp`. --- ### Trường Hợp Mỗi Vật Được Chọn Nhiều Lần ```cpp #include <bits/stdc++.h> using namespace std; int main() { // Tối ưu hóa tốc độ nhập/xuất trong C++ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // Mở file input và output freopen("VALIB.INP", "r", stdin); freopen("VALIB.OUT", "w", stdout); long long n, w; // Đọc n (số vật phẩm) và w (tổng trọng lượng tối đa cho phép) cin >> n >> w; // a[i] là trọng lượng của vật phẩm thứ i, // b[i] là giá trị (hoặc lợi ích) của vật phẩm thứ i long long a[n+1], b[n+1]; // Mảng dp[i][j] sẽ lưu giá trị tốt nhất có thể đạt được // khi xét đến i vật phẩm đầu tiên với sức chứa j static long long dp[10001][10001]; // Đọc dữ liệu trọng lượng và giá trị của từng vật phẩm for (long long i = 1; i <= n; i++) { cin >> a[i] >> b[i]; } // Khởi tạo dp với 0 for (long long i = 0; i <= n; i++) { for (long long j = 0; j <= w; j++) { dp[i][j] = 0; } } // Tính dp theo hướng dẫn trong code // Lưu ý: Ở đây dùng dp[i][j-a[i]] => kiểu cập nhật như Unbounded Knapsack // (có thể sử dụng 1 vật phẩm nhiều lần). Kiểm tra lại logic nếu bạn muốn 0-1 Knapsack. for (long long i = 1; i <= n; i++) { for (long long j = 1; j <= w; j++) { // Bước 1: Giữ nguyên giá trị nếu không lấy vật phẩm i dp[i][j] = dp[i - 1][j]; // Bước 2: Nếu có thể lấy vật phẩm i (a[i] <= j), // thì xét xem có lợi hơn nếu thêm vật phẩm i hay không // Lưu ý: dp[i][j - a[i]] (thay vì dp[i-1][j - a[i]]) cho phép dùng lại vật phẩm i if (j >= a[i]) { dp[i][j] = max(dp[i][j], dp[i][j - a[i]] + b[i]); } } } // Kết quả cuối cùng là dp[n][w], tức giá trị lớn nhất // khi đã xét tất cả n vật phẩm với sức chứa w cout << dp[n][w]; return 0; } ``` **Độ phức tạp** - **Thời gian**: $O(n * m)$, vì với mỗi trong $n$ vật phẩm, ta duyệt qua $m$ sức chứa. - **Không gian**: $O(n * m)$, do lưu một mảng 2 chiều `dp`. ## Bài tập áp dụng ## Tài liệu tham khảo - [Knapsack Problem - Wikipedia](https://en.wikipedia.org/wiki/Knapsack_problem) - [Bài toán cái túi và những ứng dụng xung quanh nó - Viblo](https://viblo.asia/p/bai-toan-cai-tui-va-nhung-ung-dung-xung-quanh-no-maGK7Nke5j2)