Bài toán dung tích lớn nhất¶

Question

Cho một mảng \(ht\), trong đó mỗi phần tử đại diện cho chiều cao của một tấm vách ngăn thẳng đứng. Bất kỳ hai vách ngăn nào trong mảng, cùng với không gian giữa chúng, đều có thể tạo thành một thùng chứa.

Dung tích của thùng chứa bằng tích của chiều cao và chiều rộng của nó (tức là diện tích của nó), trong đó chiều cao được quyết định bởi vách ngăn ngắn hơn và chiều rộng là khoảng cách giữa các chỉ số mảng của hai vách ngăn.

Chọn hai vách ngăn trong mảng sao cho dung tích của thùng chứa tạo thành là lớn nhất và trả về dung tích lớn nhất đó. Một ví dụ được thể hiện trong hình dưới đây.

Thùng chứa được tạo thành bởi hai vách ngăn bất kỳ, do đó trạng thái của bài toán này là chỉ số của hai vách ngăn, ký hiệu là \([i, j]\).

Theo đề bài, dung tích bằng chiều cao nhân với chiều rộng, trong đó chiều cao được quyết định bởi vách ngăn ngắn hơn và chiều rộng là khoảng cách giữa các chỉ số mảng của hai vách ngăn. Gọi dung tích là \(cap[i, j]\), khi đó chúng ta có công thức sau:

\[ cap[i, j] = \min(ht[i], ht[j]) \times (j - i) \]

Gọi chiều dài mảng là \(n\). Khi đó số cách chọn hai vách ngăn (tức là tổng số trạng thái) là \(C_n^2 = \frac{n(n - 1)}{2}\). Cách tiếp cận trực tiếp nhất là duyệt vét cạn (exhaustive search) tất cả các trạng thái để tìm dung tích lớn nhất, điều này có độ phức tạp thời gian là \(O(n^2)\).

Xác định chiến lược tham lam¶

Bài toán này có một lời giải hiệu quả hơn. Như hình dưới đây, hãy xem xét một trạng thái \([i, j]\) trong đó \(i < j\) và \(ht[i] < ht[j]\). Trong trường hợp này, \(i\) là vách ngăn ngắn hơn và \(j\) là vách ngăn cao hơn.

Như hình dưới đây, nếu bây giờ chúng ta dịch chuyển vách ngăn cao hơn \(j\) vào trong về phía vách ngăn ngắn hơn \(i\), dung tích chắc chắn sẽ giảm.

Điều này là do sau khi dịch chuyển vách ngăn cao hơn \(j\), chiều rộng \(j-i\) chắc chắn sẽ giảm. Vì chiều cao được quyết định bởi vách ngăn ngắn hơn, nên chiều cao chỉ có thể giữ nguyên (nếu \(i\) vẫn là vách ngăn ngắn hơn) hoặc giảm đi (nếu \(j\) trở thành vách ngăn ngắn hơn sau khi dịch chuyển).

Ngược lại, chỉ bằng cách dịch chuyển vách ngăn ngắn hơn \(i\) vào trong thì dung tích mới có khả năng tăng lên. Mặc dù chiều rộng chắc chắn sẽ giảm, nhưng chiều cao có thể tăng lên (vách ngăn mới ở \(i\) sau khi dịch chuyển có thể cao hơn). Ví dụ, trong hình dưới đây, diện tích tăng lên sau khi dịch chuyển vách ngăn ngắn hơn.

Từ đây, chúng ta có thể rút ra chiến lược tham lam (greedy strategy) cho bài toán này: khởi tạo hai con trỏ (pointer) ở hai đầu và trong mỗi lượt, dịch chuyển con trỏ tương ứng với vách ngăn ngắn hơn vào trong cho đến khi hai con trỏ gặp nhau.

Hình dưới đây thể hiện quá trình thực thi của chiến lược tham lam.

Ở trạng thái ban đầu, các con trỏ \(i\) và \(j\) nằm ở hai đầu của mảng.
Tính dung tích của trạng thái hiện tại \(cap[i, j]\) và cập nhật dung tích lớn nhất.
So sánh chiều cao của các vách ngăn \(i\) và \(j\), và dịch chuyển con trỏ tương ứng với vách ngăn ngắn hơn vào trong một vị trí.
Lặp lại bước 2. và 3. cho đến khi \(i\) và \(j\) gặp nhau.

Triển khai mã nguồn¶

Mã nguồn chạy tối đa \(n\) lượt, do đó độ phức tạp thời gian (time complexity) là \(O(n)\).

Các biến \(i\), \(j\) và \(res\) chỉ sử dụng một lượng không gian phụ trợ hằng số, do đó độ phức tạp không gian (space complexity) là \(O(1)\).

[file]{max_capacity}-[class]{}-[func]{max_capacity}

Chứng minh tính đúng đắn¶

Lý do thuật toán tham lam nhanh hơn so với duyệt vét cạn là vì mỗi lượt lựa chọn tham lam "bỏ qua" một số trạng thái.

Ví dụ, trong trạng thái \(cap[i, j]\), giả sử \(i\) là vách ngăn ngắn hơn và \(j\) là vách ngăn cao hơn. Nếu chúng ta dịch chuyển một cách tham lam vách ngăn ngắn hơn \(i\) vào trong một vị trí, các trạng thái thể hiện trong hình dưới đây sẽ bị "bỏ qua". Điều này có nghĩa là dung tích của chúng không còn được kiểm tra sau đó nữa.

\[ cap[i, i+1], cap[i, i+2], \dots, cap[i, j-2], cap[i, j-1] \]

Xem xét kỹ hơn sẽ thấy rằng các trạng thái bị bỏ qua này chính là các trạng thái thu được bằng cách dịch chuyển vách ngăn cao hơn \(j\) vào trong. Chúng ta đã chứng minh rằng việc dịch chuyển vách ngăn cao hơn vào trong chắc chắn sẽ làm giảm dung tích. Do đó, không có trạng thái nào bị bỏ qua có thể là lời giải tối ưu (optimal solution), vì vậy việc bỏ qua chúng không làm chúng ta bỏ lỡ lời giải tối ưu.

Phân tích trên chỉ ra rằng việc dịch chuyển vách ngăn ngắn hơn là một thao tác "an toàn" và chiến lược tham lam là hiệu quả.