Bài 26: Xếp hàng vào thùng và chọn đơn cho xe giao hàng – Bài toán cái túi và bài toán xếp thùng

Mỗi ngày, các kho thương mại điện tử phải trả lời hàng triệu câu hỏi nhỏ: xe giao hàng chở được 10 kg thì nên chở những đơn nào? Mười món hàng này cần ít nhất mấy thùng? Đây là hai bài toán kinh điển của tin học: bài toán cái túi và bài toán xếp thùng.

Bài thứ hai mươi sáu của chuyên mục "Thuật toán trong đời sống": bài toán cái túi, bài toán xếp thùng và kho hàng thông minh.

1. Bài toán cái túi: chọn đơn nào lên xe?

Một xe giao hàng chở tối đa 10 kg. Có 5 đơn hàng, mỗi đơn có khối lượng và phí ship khác nhau. Chọn những đơn nào để tổng phí lớn nhất mà không quá tải?

Thử hết mọi cách chọn thì với n đơn có 2ⁿ cách – 50 đơn đã là hơn một triệu tỷ cách. Lời giải hay hơn là quy hoạch động: best[w] là phí lớn nhất khi tổng khối lượng không quá w kg; xét lần lượt từng đơn và cập nhật bảng.

2. Bài toán xếp thùng: cần ít nhất mấy thùng?

Có 10 món hàng với thể tích khác nhau, mỗi thùng chứa được 10 đơn vị. Hai chiến lược tham lam:

• Next Fit: xếp lần lượt, thùng hiện tại đầy thì mở thùng mới.
• First Fit Decreasing (FFD): sắp xếp món to trước, mỗi món bỏ vào thùng đầu tiên còn đủ chỗ.

Bài toán cái túi và xếp thùng

#include <bits/stdc++.h>
using namespace std;
int main(){
    // Phần 1 – Cái túi 0/1: xe chở tối đa 10 kg, chọn đơn có tổng phí ship lớn nhất
    vector<tuple<string,int,int>> orders = {{"Ao",1,15},{"Giay",3,30},{"Noi com",5,45},{"Sach",4,40},{"Quat",6,50}};
    const int CAP = 10;
    vector<int> best(CAP + 1, 0); vector<vector<string>> pick(CAP + 1);
    for(auto& [name, w, v] : orders)
        for(int c = CAP; c >= w; c--)                 // duyệt ngược: mỗi đơn chọn tối đa 1 lần
            if(best[c - w] + v > best[c]){ best[c] = best[c - w] + v; pick[c] = pick[c - w]; pick[c].push_back(name); }
    cout << "Cai tui:";
    for(auto& s : pick[CAP]) cout << " [" << s << "]";
    cout << " phi = " << best[CAP] << " nghin dong\n";
    // Phần 2 – Xếp hàng vào thùng sức chứa 10
    vector<int> items = {2, 5, 4, 7, 1, 3, 8, 6, 4, 2};
    int nf = 1, cur = 0;                              // Next Fit
    for(int x : items){ if(cur + x > 10){ nf++; cur = 0; } cur += x; }
    vector<int> a = items; sort(a.rbegin(), a.rend()); vector<int> load;   // First Fit Decreasing
    for(int x : a){
        bool ok = false;
        for(int& b : load) if(b + x <= 10){ b += x; ok = true; break; }
        if(!ok) load.push_back(x);
    }
    int total = accumulate(items.begin(), items.end(), 0);
    printf("Next Fit: %d thung\nFirst Fit Decreasing: %d thung\nCan it nhat: %d thung (tong the tich %d)\n",
           nf, (int)load.size(), (total + 9) / 10, total);
}

# Phần 1 – Bài toán cái túi: xe giao hàng chở tối đa 10 kg, chọn đơn hàng có tổng phí ship lớn nhất
orders = [("Ao", 1, 15), ("Giay", 3, 30), ("Noi com", 5, 45), ("Sach", 4, 40), ("Quat", 6, 50)]
CAP = 10
best = [0] * (CAP + 1)                       # best[w]: phí lớn nhất khi tổng khối lượng <= w
pick = [[] for _ in range(CAP + 1)]
for name, w, v in orders:
    for c in range(CAP, w - 1, -1):          # duyệt ngược để mỗi đơn chỉ chọn 1 lần
        if best[c - w] + v > best[c]:
            best[c] = best[c - w] + v; pick[c] = pick[c - w] + [name]
print("Cai tui:", pick[CAP], "phi =", best[CAP], "nghin dong")

# Phần 2 – Xếp hàng vào thùng (bin packing): thùng chứa được 10 đơn vị thể tích
items = [2, 5, 4, 7, 1, 3, 8, 6, 4, 2]
def next_fit(a):
    boxes = [[]]
    for x in a:                              # thùng hiện tại đầy thì mở thùng mới
        if sum(boxes[-1]) + x > 10: boxes.append([])
        boxes[-1].append(x)
    return boxes
def first_fit_decreasing(a):
    boxes = []
    for x in sorted(a, reverse=True):        # xếp món to trước
        for b in boxes:
            if sum(b) + x <= 10: b.append(x); break
        else: boxes.append([x])
    return boxes
print("Next Fit:", len(next_fit(items)), "thung")
print("First Fit Decreasing:", len(first_fit_decreasing(items)), "thung", first_fit_decreasing(items))
print(f"Can it nhat: {-(-sum(items) // 10)} thung (tong the tich {sum(items)})")

Kết quả chạy (bản Python):

Cai tui: ['Ao', 'Noi com', 'Sach'] phi = 100 nghin dong
Next Fit: 7 thung
First Fit Decreasing: 5 thung [[8, 2], [7, 3], [6, 4], [5, 4, 1], [2]]
Can it nhat: 5 thung (tong the tich 42)

Xe nên chở áo, nồi cơm và sách: vừa đủ 10 kg, phí 100 nghìn đồng. Với việc xếp thùng, chỉ cần xếp món to trước, FFD giảm từ 7 xuống 5 thùng – bằng đúng giới hạn dưới (tổng thể tích 42 cần ít nhất 5 thùng loại 10), nên đây là đáp án tối ưu.

3. Hai bài toán "khó" nổi tiếng

• Năm 1972, Richard Karp công bố danh sách 21 bài toán NP-đầy đủ nổi tiếng, trong đó có bài toán dạng cái túi (gần với bài toán tổng tập con). Quy hoạch động ở trên chỉ nhanh khi sức chứa nhỏ.
• Bài toán xếp thùng là NP-khó: chưa ai biết thuật toán nhanh luôn cho đáp án tối ưu. Nhưng FFD được chứng minh là rất tốt: năm 2007, György Dósa chứng minh FFD không bao giờ dùng quá 11/9 × số thùng tối ưu + 6/9 thùng.

Trong thực tế, "gần tối ưu nhưng chạy rất nhanh" thường quý hơn "tối ưu nhưng chạy mãi không xong" – nhất là khi mỗi giây kho hàng phải xử lý hàng trăm đơn.

4. Kho hàng ngoài đời

• Amazon (4/2024) cho biết họ dùng mô hình AI tên Package Decision Engine: camera chụp từng món hàng, mô hình kết hợp thị giác máy tính và xử lý ngôn ngữ để chọn cách đóng gói phù hợp (hộp, túi đệm hay không cần thêm bao bì). Theo Amazon, cùng với các cải tiến khác, từ năm 2015 hãng đã tránh được hơn 2 triệu tấn vật liệu đóng gói.
• Shopee: theo báo Doanh nghiệp Hội nhập (5/2025), đơn vị vận chuyển SPX Express xây trung tâm phân loại tự động rộng 170.000 m² tại Hưng Yên, công suất tới 7 triệu đơn mỗi ngày, dự kiến hoàn thành năm 2027.

Các công ty không công bố chi tiết thuật toán họ dùng; cái túi và xếp thùng ở đây là mô hình đơn giản giúp hiểu bản chất của việc "xếp sao cho vừa".

5. Bạn học được gì từ đây?

• Quy hoạch động cái túi là dạng bài kinh điển trong đề HSG Tin.
• Sắp xếp trước có thể làm thuật toán tham lam tốt hơn hẳn.
• Biết bài toán là NP-khó giúp ta chọn đúng hướng: tìm lời giải đủ tốt thay vì cố tìm lời giải hoàn hảo.

Bài tập luyện tập

• CSES – Book Shop (bài toán cái túi 0/1)
• CSES – Ferris Wheel (ghép cặp vào cabin – tham lam sau khi sắp xếp)
• Tìm một bộ dữ liệu mà FFD dùng nhiều thùng hơn đáp án tối ưu.

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 27: Thu nhỏ ảnh mà không làm méo người – Thuật toán seam carving và quy hoạch động

Đọc tiếp: seam carving & QHĐ →

← Bài trước: robot hút bụi & BFSXem tất cả 27 bài →

Nguồn tham khảo

• Amazon (16/04/2024) – How Amazon is using AI to reduce packaging
• Wikipedia – Karp's 21 NP-complete problems
• Wikipedia – First-fit-decreasing bin packing (cận của Dósa, 2007)
• Doanh nghiệp Hội nhập (29/05/2025) – Shopee xây trung tâm phân loại tự động lớn nhất Đông Nam Á tại Việt Nam