- Vật đang xếp
- Vừa
- Không vừa
Bài toán xếp thùng
Hộp lên xe tải, tệp vào ổ đĩa, công việc lên máy: bài toán xếp thùng hỏi làm sao xếp một danh sách vật vào càng ít thùng bằng nhau càng tốt. Chưa biết phương pháp nhanh nào luôn tìm ra cách xếp tốt nhất, nhưng các quy tắc đơn giản cho kết quả khá sát. Hãy chọn một quy tắc, đi qua từng bước và so sánh với đáp án chính xác. Chạm vào một vật trên kệ, rồi chạm vào thùng muốn đặt nó vào: thùng màu xanh lá còn chỗ cho nó, còn Thùng mới mở thêm một thùng. Chạm vào một vật trong thùng để lấy nó ra lại. Hãy xếp mọi vật vào càng ít thùng càng tốt; cận dưới (tổng khối lượng chia cho cỡ thùng, làm tròn lên) và số ít nhất có thể cho thấy bạn đã gần tới đâu, còn Ít thùng nhất cho thấy cách xếp tốt nhất. Thay đổi khối lượng các vật (tính bằng kilôgam) và cỡ thùng trong bảng điều khiển. Chế độ xem Từng bước cho thấy các quy tắc nhanh xếp như thế nào: next fit, first fit hoặc best fit, trên các vật theo thứ tự đã nhập hoặc sắp xếp từ lớn đến nhỏ, hoặc đáp án chính xác do quy hoạch động tìm ra. Nhấn Phát để xem các vật được xếp vào thùng, hoặc Bước và Lùi để đi từng bước một, và kéo thanh trượt bước để nhảy tới bất kỳ đâu. Khi khu xếp thùng được chọn, các phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy tới đầu và cuối.
Cách nó hoạt động
- Chạm vào một đồ vật, rồi chạm vào thùng còn chỗ để bỏ vào, hoặc Thùng mới để mở thêm thùng.
- Hãy cố dùng ít thùng nhất có thể, hoặc nhấn Ít thùng nhất để xem cách xếp tốt nhất.
- Mở chế độ xem Từng bước, chọn một quy tắc và nhấn Phát để xem mỗi đồ vật thử các thùng.
Các quy tắc
Next fit chỉ giữ thùng cuối cùng mở: vật nào không vừa ở đó sẽ bắt đầu một thùng mới. First fit thử các thùng từ thùng đầu tiên và chọn thùng đầu tiên còn chỗ. Best fit thử mọi thùng và chọn thùng đầy nhất còn chỗ, để lại ít chỗ trống nhất. First fit và best fit cũng có thể sắp xếp các vật từ lớn đến nhỏ trước, tạo thành first fit decreasing và best fit decreasing.
Đáp án chính xác
Quy tắc cuối không phải là quy tắc kinh nghiệm: nó tìm số thùng ít nhất bằng quy hoạch động trên các tập vật. Với mỗi tập vật, nó lưu số thùng ít nhất chứa được chúng và, trong các cách xếp dùng số thùng đó, lượng chứa nhỏ nhất ở thùng cuối. Mỗi lần, một tập lớn thêm một vật; vật này hoặc được thêm vào thùng cuối, hoặc mở một thùng mới. Với n vật có 2ⁿ tập, đó là lý do ứng dụng chỉ cho phép tối đa 12 vật. Cận dưới, tức tổng kích thước chia cho kích thước thùng rồi làm tròn lên, cho thấy một cách xếp gần tối ưu đến mức nào.
Câu hỏi thường gặp
Quy tắc xếp thùng nào tốt nhất?
Trong các quy tắc nhanh, first fit decreasing và best fit decreasing mạnh nhất: chúng không bao giờ dùng nhiều hơn 11/9 số thùng ít nhất, cộng một hằng số nhỏ. First fit và best fit trên các vật chưa sắp xếp không vượt quá 1,7 lần số thùng ít nhất, còn next fit không vượt quá 2 lần.
Vì sao bài toán xếp thùng khó?
Chỉ riêng việc quyết định các vật có vừa trong hai thùng hay không đã là bài toán phân hoạch, vốn là NP-đầy đủ. Vì vậy, trừ khi P = NP, không có phương pháp nào tìm nhanh số thùng ít nhất cho mọi đầu vào, và các phương pháp chính xác cần thời gian mũ trong trường hợp xấu nhất.
Cận dưới là gì?
Tổng kích thước các vật chia cho kích thước thùng, làm tròn lên. Không cách xếp nào dùng ít thùng hơn được, vì các thùng phải chứa hết mọi vật. Cách xếp tốt nhất thường bằng cận dưới, nhưng không phải luôn luôn: ba vật cỡ 6 với thùng cỡ 10 có cận dưới là 2 nhưng cần 3 thùng.
Đây có phải là quy hoạch động không?
Đáp án chính xác thì đúng vậy: nó xây dựng cách xếp tốt nhất cho mỗi tập vật từ các cách xếp tốt nhất của những tập nhỏ hơn. Các quy tắc nhanh là phương pháp tham lam, quyết định một lần và không bao giờ nhìn lại.
Có dữ liệu nào được gửi đi đâu không?
Không. Mọi thứ đều được tính trong trình duyệt của bạn, và thiết lập gần nhất của bạn được lưu trong bộ nhớ cục bộ của trình duyệt này.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Tới trình chỉnh sửa