Bài toán xếp thùng hỏi: có một đống đồ kích thước khác nhau và nhiều thùng giống nhau, cần ít thùng nhất là bao nhiêu để chứa hết. Nghe đơn giản, nhưng toán học đã chứng minh đây là bài toán thuộc loại NP-khó: chưa ai biết cách nào luôn tìm ra lời giải tốt nhất mà không phải thử số trường hợp tăng vọt theo số món đồ. Tin vui là có những mẹo rất đơn giản, đứng đầu là "xếp vật lớn trước", cho kết quả không bao giờ tệ hơn tối ưu quá nhiều.
Bài toán xếp thùng là gì?
Trong sách toán ứng dụng, bài toán xếp thùng (tiếng Anh: bin packing) thường được phát biểu ở dạng một chiều cho dễ hình dung. Mỗi thùng có sức chứa 1. Mỗi món đồ có kích thước là một số nằm giữa 0 và 1, ví dụ 0,5; 0,7; 0,2. Việc cần làm là chia các món vào thùng sao cho tổng trong mỗi thùng không vượt quá 1, và số thùng dùng là ít nhất.
Đời thật thì "kích thước" có thể là thể tích, là cân nặng, là thời lượng. Một vài dạng quen mặt:
- Chia đồ vào các hộp cùng cỡ khi dọn kho.
- Chia các tệp lớn nhỏ vào những ổ nhớ cùng dung lượng.
- Chia việc vào các ca làm việc cùng số giờ.
- Cắt những đoạn ống, đoạn gỗ ngắn từ các thanh dài bằng nhau sao cho ít thanh nhất (bài toán cắt vật liệu, họ hàng gần của xếp thùng).
Khi chuyển sang hai chiều (xếp hình chữ nhật lên tấm phẳng) và ba chiều (xếp hộp vào khối hộp), bài toán còn khó hơn nữa, vì ngoài chuyện chọn món nào vào thùng nào còn phải chọn đặt ở đâu, xoay chiều nào.
Vì sao máy tính cũng khó tìm cách xếp tốt nhất?
Cách "ngây thơ" để chắc chắn tìm được lời giải tốt nhất là thử mọi cách chia. Với 10 món, số cách chia đã lên tới hàng chục nghìn. Với 30 món, con số vượt xa khả năng thử hết của mọi máy tính hiện có. Số trường hợp không tăng đều mà tăng theo kiểu bùng nổ: thêm một món là nhân lên chứ không cộng thêm.
Các nhà tin học xếp bài toán xếp thùng vào nhóm NP-khó. Michael Garey và David Johnson đưa nó vào danh mục kinh điển trong cuốn sách năm 1979 về các bài toán khó tính toán. Nói gọn, điều đó có nghĩa:
- Nếu đã có sẵn một cách xếp, kiểm tra xem nó có hợp lệ không thì rất nhanh.
- Nhưng tìm ra cách xếp ít thùng nhất thì, theo hiểu biết hiện nay, không có công thức nhanh cho mọi trường hợp.
- Nếu ai tìm được cách giải nhanh cho bài này, người đó cũng giải được hàng loạt bài khó khác, kể cả câu hỏi "P có bằng NP không" vốn là một trong bảy bài toán thiên niên kỷ do Viện Toán học Clay nêu năm 2000.
Trên thực tế, phần mềm vẫn giải chính xác được những bài vài chục, vài trăm món nhờ cắt tỉa thông minh, không phải thử hết. Nhưng với bài lớn, người ta chấp nhận lời giải "đủ tốt" từ các quy tắc nhanh.
Mẹo "xếp vật lớn trước" tốt tới mức nào?
Có ba quy tắc dễ nhớ, đi từ thô tới tinh:
| Quy tắc | Cách làm | Tệ nhất là bao nhiêu (so với tối ưu) |
|---|---|---|
| Thùng kế tiếp (Next Fit) | Cầm từng món theo thứ tự có sẵn, bỏ vào thùng đang mở; không vừa thì đóng thùng, mở thùng mới | Có thể dùng gần gấp đôi số thùng cần thiết |
| Thùng đầu tiên vừa (First Fit) | Mỗi món bỏ vào thùng đầu tiên còn chỗ, xét từ thùng số 1 | Khoảng 1,7 lần tối ưu |
| Lớn trước rồi thùng đầu tiên vừa (First Fit Decreasing) | Sắp món từ to đến nhỏ, rồi làm như trên | Khoảng 11/9 lần tối ưu, tức hơn chừng 22%, cộng thêm một hằng số nhỏ |
Con số 11/9 cho quy tắc "lớn trước" được David Johnson chứng minh trong luận án năm 1973, về sau các nhà toán học siết chặt phần hằng số đi kèm. Đây là cận "tệ nhất có thể": phải dựng những bộ đồ được thiết kế rất khéo mới làm quy tắc này lãng phí tới mức đó. Với đồ đạc đời thường, nó thường cho kết quả bằng hoặc gần bằng tối ưu.
Vì sao xếp lớn trước lại hiệu quả?
Món to là món khó tìm chỗ. Nếu để cuối, lúc đó các thùng đã lấp lửng bởi đồ nhỏ, món to không chen vào đâu được và buộc phải mở thùng mới gần như trống. Ngược lại, xếp món to trước thì các khe còn lại được đồ nhỏ lấp dần, như rót cát vào giữa những viên đá. Đồ nhỏ "linh hoạt", đồ to "khó tính"; cho kẻ khó tính chọn chỗ trước.
Ví dụ tự làm bằng giấy
Lấy sức chứa thùng là 10. Đồ có cỡ: 2, 5, 4, 7, 1, 3, 8, 6.
- Theo thứ tự có sẵn, thùng đầu tiên vừa: thùng 1 nhận 2, 5, 1 (còn trống 2), thùng 2 nhận 4, 3 (còn 3), thùng 3 nhận 7, thùng 4 nhận 8, thùng 5 nhận 6. Kết quả 5 thùng.
- Lớn trước: sắp lại 8, 7, 6, 5, 4, 3, 2, 1. Thùng 1 nhận 8 rồi 2. Thùng 2 nhận 7 rồi 3. Thùng 3 nhận 6 rồi 4. Thùng 4 nhận 5 rồi 1. Kết quả 4 thùng.
Tổng các món là 36, mỗi thùng chứa 10, nên ít nhất phải 4 thùng. Quy tắc "lớn trước" chạm đúng mức tối thiểu này.
Xếp hộp ba chiều khó hơn ở chỗ nào?
Khi đồ có dài, rộng, cao, cộng thể tích lại chỉ cho một cận dưới: tổng thể tích đồ là 80 lít không có nghĩa thùng 80 lít chứa vừa. Lý do:
- Hình dạng không khớp nhau. Hai hộp vuông 30 cm không lọt vào khoảng trống dài 50 cm dù diện tích khe đủ lớn.
- Có chiều xoay. Một hộp chữ nhật có sáu cách đặt. Chọn sai chiều là phí một lớp.
- Có trọng lực và độ bền. Đồ nặng phải ở dưới, đồ dễ móp không chịu được sức đè, đồ cần lấy thường phải ở ngoài. Toán thuần tuý bỏ qua, đời thật thì không.
- Đồ mềm và đồ cứng. Túi vải, áo quần biến dạng lấp khe được, hộp cứng thì không.
Vì thế, các bài xếp hộp ba chiều trong logistics thường được giải bằng phần mềm chuyên dụng chạy các quy tắc kiểu "lớn trước, sát góc trước", rồi người xếp chỉnh tay.
Áp vào xếp tủ, xếp cốp xe thế nào?
Những điều toán học dạy có thể rút thành vài thói quen dùng ngay:
Bốn bước khi xếp một khoang chứa
- Bày hết ra trước khi xếp. Thuật toán tốt cần "nhìn thấy" toàn bộ đồ. Xếp từng món theo thứ tự cầm lên chính là quy tắc "thùng kế tiếp", loại kém nhất trong bảng trên.
- Đặt món to, cứng, nặng trước, sát đáy và sát vách trong cùng. Chúng tạo "khung" cho phần còn lại.
- Chọn chiều xoay để lấp kín một mặt. Thử đặt món to theo chiều mà cạnh của nó cộng lại gần bằng bề ngang khoang. Ví dụ cốp sâu 90 cm thì hai hộp sâu 45 cm khít hơn một hộp 60 cm cộng khoảng hở 30 cm.
- Dồn đồ mềm, đồ nhỏ vào khe cuối cùng. Đây là phần "cát lấp giữa đá".
Biết dừng ở "đủ tốt"
Bài toán đã khó với máy tính thì đừng mong tìm cách xếp hoàn hảo trong năm phút. Mục tiêu hợp lý là xếp đủ chỗ, chắc chắn, dễ lấy. Với tủ đồ dùng hằng ngày, một cách xếp hơi phí chỗ nhưng lấy ra cất vào nhanh thường đáng giá hơn cách xếp khít tới từng phân mà mỗi lần lấy phải dỡ cả tủ. Còn chuyện xếp vali đi xa hay xếp hàng lên xe tải là những bài riêng, có kỹ thuật riêng.
Những bài toán "anh em" với xếp thùng
Xếp thùng hay bị nhầm với một vài bài toán gần giống. Phân biệt được thì biết mình đang đối mặt với loại nào:
| Bài toán | Câu hỏi | Ví dụ đời thường |
|---|---|---|
| Xếp thùng | Ít thùng nhất để chứa hết đồ | Dọn nhà vào bao nhiêu hộp |
| Cái túi (knapsack) | Một thùng duy nhất, chọn đồ nào để tổng giá trị lớn nhất | Chỉ mang được một ba lô, chọn món nào quan trọng nhất |
| Cắt vật liệu | Cắt các đoạn ngắn từ ít thanh dài nhất | Cắt ống nước, thanh nhôm, gỗ nẹp |
| Xếp dải (strip packing) | Bề ngang cố định, xếp sao cho chiều dài dùng ít nhất | Cắt hình trên cuộn vải, cuộn tôn |
Cả bốn đều thuộc nhóm khó tính toán, và cả bốn đều có mẹo "lớn trước" hoặc "đáng giá nhất trên mỗi đơn vị chỗ trước" làm điểm xuất phát tốt.
Góc nhìn hôm nay: tự tập với một hộp đồ
Một cách thú vị để thấm bài toán này là tự làm thí nghiệm nhỏ. Cắt giấy bìa thành 12 dải có chiều dài ngẫu nhiên từ 1 đến 9 phân, kẻ trên bàn vài "thùng" dài 10 phân. Lần đầu xếp theo thứ tự rút ra, lần hai sắp từ dài đến ngắn rồi xếp. Ghi số thùng mỗi lần. Đa số lần, cách thứ hai dùng ít thùng hơn hoặc bằng.
Muốn đọc thêm, sách nhập môn về thuật toán và tối ưu tổ hợp dành nguyên một chương cho bin packing; tài liệu lập trình thi đấu cũng có nhiều bài luyện. Ý cần mang về chỉ gói trong một câu: khi không chắc, cho món khó tính nhất chọn chỗ trước.
Câu hỏi thường gặp
Bài toán xếp thùng (bin packing) là gì?
Đó là bài toán chia các món đồ có kích thước khác nhau vào những thùng cùng sức chứa sao cho dùng ít thùng nhất. Nó xuất hiện trong dọn kho, chia tệp vào ổ nhớ, cắt vật liệu, lập lịch ca làm việc.
Vì sao bài toán xếp thùng được gọi là bài toán khó?
Vì số cách chia tăng bùng nổ theo số món đồ, và theo hiểu biết hiện nay không có phương pháp nhanh nào luôn tìm ra lời giải tốt nhất cho mọi trường hợp. Các nhà tin học xếp nó vào nhóm NP-khó.
Mẹo xếp đồ vào thùng đơn giản mà hiệu quả là gì?
Sắp đồ từ lớn đến nhỏ, rồi lần lượt bỏ mỗi món vào thùng đầu tiên còn đủ chỗ. Quy tắc này được chứng minh không bao giờ dùng quá khoảng 11/9 số thùng tối ưu, cộng một hằng số nhỏ.
Tổng thể tích đồ bằng thể tích thùng thì có xếp vừa không?
Chưa chắc. Tổng thể tích chỉ là mức tối thiểu; hình dạng không khớp, chiều xoay, đồ cứng không biến dạng đều tạo khoảng hở. Thực tế nên chừa dư một phần thể tích.
Bài toán xếp thùng khác bài toán cái túi thế nào?
Xếp thùng hỏi cần ít thùng nhất để chứa hết đồ. Bài toán cái túi chỉ có một túi và hỏi nên chọn những món nào để tổng giá trị mang theo là lớn nhất.
