Bài toán Balo 0-1¶
Bài toán balo (knapsack problem) là một bài toán nhập môn tuyệt vời cho quy hoạch động và là một trong những dạng bài toán phổ biến nhất trong quy hoạch động. Nó có nhiều biến thể, chẳng hạn như bài toán balo 0-1 (0-1 knapsack problem), bài toán balo vô hạn (unbounded knapsack problem) và bài toán balo bội (multiple knapsack problem).
Trong phần này, trước tiên chúng ta sẽ giải quyết bài toán balo 0-1 phổ biến nhất.
Question
Cho \(n\) đồ vật và một chiếc balo có sức chứa \(cap\), trong đó trọng lượng và giá trị của đồ vật thứ \(i\) lần lượt là \(wgt[i-1]\) và \(val[i-1]\). Mỗi đồ vật chỉ được chọn tối đa một lần. Hỏi giá trị lớn nhất có thể xếp vào balo trong giới hạn sức chứa là bao nhiêu?
Quan sát hình bên dưới. Vì đồ vật số \(i\) bắt đầu đếm từ \(1\) và chỉ số mảng bắt đầu từ \(0\), đồ vật \(i\) tương ứng với trọng lượng \(wgt[i-1]\) và giá trị \(val[i-1]\).
Chúng ta có thể xem bài toán balo 0-1 như một quy trình gồm \(n\) vòng ra quyết định, trong đó đối với mỗi đồ vật sẽ có hai quyết định: không bỏ vào balo và bỏ vào balo, do đó bài toán thỏa mãn mô hình cây quyết định.
Mục tiêu của bài toán này là tìm "giá trị lớn nhất có thể xếp vào balo trong giới hạn sức chứa", vì vậy khả năng cao nó là một bài toán quy hoạch động.
Bước 1: Suy nghĩ về quyết định trong từng vòng, định nghĩa trạng thái, và từ đó thu được bảng \(dp\)
Đối với mỗi đồ vật, nếu không bỏ vào balo, sức chứa của balo vẫn giữ nguyên; nếu bỏ vào balo, sức chứa của balo sẽ giảm đi. Từ đó, chúng ta có thể suy ra định nghĩa trạng thái: đồ vật hiện tại số \(i\) và sức chứa balo \(c\), được ký hiệu là \([i, c]\).
Trạng thái \([i, c]\) tương ứng với bài toán con: giá trị lớn nhất khi chọn từ \(i\) đồ vật đầu tiên với balo có sức chứa \(c\), được ký hiệu là \(dp[i, c]\).
Điều chúng ta cần tìm là \(dp[n, cap]\), vì vậy chúng ta cần một bảng \(dp\) hai chiều kích thước \((n+1) \times (cap+1)\).
Bước 2: Xác định cấu trúc con tối ưu, từ đó rút ra phương trình chuyển trạng thái
Sau khi đưa ra quyết định cho đồ vật thứ \(i\), phần còn lại là bài toán con của \(i-1\) đồ vật đầu tiên, có thể chia thành hai trường hợp sau.
- Không bỏ đồ vật \(i\): Sức chứa của balo giữ nguyên, và trạng thái chuyển thành \([i-1, c]\).
- Bỏ đồ vật \(i\): Sức chứa của balo giảm đi một lượng \(wgt[i-1]\), giá trị tăng lên \(val[i-1]\), và trạng thái chuyển thành \([i-1, c-wgt[i-1]]\).
Phân tích trên tiết lộ cấu trúc con tối ưu của bài toán này: giá trị tối đa \(dp[i, c]\) bằng giá trị lớn hơn thu được giữa hai phương án: không bỏ đồ vật \(i\) vào balo và bỏ đồ vật \(i\) vào balo. Từ đây, phương trình chuyển trạng thái được rút ra:
Lưu ý rằng nếu trọng lượng của đồ vật hiện tại \(wgt[i - 1]\) vượt quá sức chứa còn lại \(c\) của balo, thì lựa chọn duy nhất là không bỏ đồ vật đó vào balo.
Bước 3: Xác định điều kiện biên và thứ tự chuyển trạng thái
Khi không có đồ vật nào hoặc sức chứa balo bằng \(0\), giá trị tối đa bằng \(0\), nghĩa là cột đầu tiên \(dp[i, 0]\) và dòng đầu tiên \(dp[0, c]\) đều bằng \(0\).
Trạng thái hiện tại \([i, c]\) chuyển đổi từ trạng thái ngay phía trên \([i-1, c]\) và trạng thái phía trên bên trái \([i-1, c-wgt[i-1]]\), vì vậy chúng ta có thể duyệt qua toàn bộ bảng \(dp\) theo thứ tự xuôi bằng hai vòng lặp lồng nhau.
Dựa trên phân tích trên, tiếp theo chúng ta sẽ lần lượt triển khai các lời giải tìm kiếm vét cạn, đệ quy có nhớ và quy hoạch động.
Phương pháp 1: Tìm kiếm vét cạn¶
Mã nguồn tìm kiếm bao gồm các yếu tố sau.
- Tham số đệ quy: trạng thái \([i, c]\).
- Giá trị trả về: lời giải của bài toán con \(dp[i, c]\).
- Điều kiện dừng: khi không còn đồ vật nào (\(i = 0\)) hoặc sức chứa còn lại của balo bằng \(0\), kết thúc đệ quy và trả về giá trị \(0\).
- Cắt nhánh: nếu trọng lượng của đồ vật hiện tại vượt quá sức chứa còn lại của balo, chỉ có thể chọn phương án không bỏ đồ vật đó vào.
Như hình dưới đây, vì mỗi đồ vật tạo ra hai nhánh tìm kiếm là loại bỏ và đưa vào, nên độ phức tạp thời gian là \(O(2^n)\).
Quan sát cây đệ quy, dễ dàng thấy được các bài toán con trùng lặp, chẳng hạn như \(dp[1, 10]\). Khi có nhiều đồ vật, sức chứa balo lớn, và đặc biệt là có nhiều đồ vật cùng trọng lượng, số lượng bài toán con trùng lặp sẽ tăng lên đáng kể.
Phương pháp 2: Đệ quy có nhớ¶
Để đảm bảo các bài toán con trùng lặp chỉ được tính toán một lần, chúng ta sử dụng một mảng ghi nhớ mem để lưu trữ lời giải của các bài toán con, trong đó mem[i][c] tương ứng với \(dp[i, c]\).
Sau khi đưa đệ quy có nhớ vào, độ phức tạp thời gian phụ thuộc vào số lượng bài toán con, tức là \(O(n \times cap)\). Mã nguồn triển khai như sau:
Hình dưới đây cho thấy các nhánh tìm kiếm được cắt bỏ khi có nhớ.
Phương pháp 3: Quy hoạch động¶
Quy hoạch động thực chất là quá trình điền vào bảng \(dp\) trong các lần chuyển trạng thái. Mã nguồn như sau:
Như hình dưới đây, cả độ phức tạp thời gian và không gian đều được xác định bởi kích thước của mảng dp, tức là \(O(n \times cap)\).
Tối ưu hóa không gian¶
Vì mỗi trạng thái chỉ liên quan đến trạng thái ở dòng ngay phía trên nó, chúng ta có thể sử dụng hai mảng cuộn tịnh tiến để giảm độ phức tạp không gian từ \(O(n^2)\) xuống \(O(n)\) (ở đây cụ thể là \(O(cap)\)).
Suy nghĩ xa hơn, liệu chúng ta có thể đạt được tối ưu hóa không gian bằng cách chỉ sử dụng một mảng duy nhất hay không? Quan sát kỹ, chúng ta thấy rằng mỗi trạng thái được chuyển đổi từ ô trực tiếp phía trên hoặc ô ở phía trên bên trái nó. Nếu chỉ có một mảng, khi chúng ta bắt đầu duyệt qua dòng \(i\), mảng đó vẫn lưu trữ trạng thái của dòng \(i-1\).
- Nếu duyệt xuôi, khi duyệt đến \(dp[j]\), các giá trị phía trên bên trái \(dp[1]\) đến \(dp[j-1]\) đã bị ghi đè thành trạng thái mới của dòng \(i\), từ đó cản trở việc chuyển trạng thái chính xác.
- Nếu duyệt ngược, vấn đề ghi đè này sẽ không xảy ra và quá trình chuyển trạng thái có thể tiến hành một cách chuẩn xác.
Hình dưới đây biểu diễn quá trình chuyển đổi từ dòng \(i = 1\) sang dòng \(i = 2\) bằng mảng đơn. Hãy suy nghĩ về sự khác biệt giữa duyệt xuôi và duyệt ngược.
Trong triển khai mã nguồn, chúng ta chỉ cần xóa chiều thứ nhất \(i\) của mảng dp và thay đổi vòng lặp trong thành duyệt ngược: