Tôi có Hộp có chiều dài, chiều rộng, chiều cao kích thước.Điền thuật toán khối lượng
Tôi có các mục có chiều dài, chiều rộng, chiều cao khác nhau.
Có một thuật toán hiện có có thể xác định các mục tốt nhất để sử dụng để đặt bên trong hộp không?
Điều này được gọi là vấn đề về đóng gói/cắt thùng/vấn đề Knapsack, và nó là NP cứng. Nói chung bạn chỉ có thể nhận được một giải pháp gần đúng bằng cách sử dụng công nghệ tự động, xem ví dụ
http://en.wikipedia.org/wiki/Knapsack_problem
Nó không phải của họ. Bạn có thể giải thích bất kỳ xấp xỉ nào cho nó? –
Tất cả các thuật toán này giúp bạn tối ưu hóa không bị chặn, ít nhất là trong một chiều, không gian. Điều cần thiết là lựa chọn tốt nhất các mặt hàng có sẵn cho các kích thước hộp hữu hạn. –
Nó có thể không khớp chính xác với chúng. Nhưng tất cả chúng đều liên quan chặt chẽ. Ví dụ. một thùng rác đóng gói với một thùng trở thành một vấn đề khác. Trong bài toán học, loại vấn đề này thường được gọi là "vấn đề đóng gói ba chiều". Một tìm kiếm học giả cung cấp khá nhiều kết quả http://scholar.google.com/scholar?q=box+packing+problem –
này có lẽ không phải là thực sự là một câu trả lời, nhưng tôi tin rằng câu trả lời là rằng vấn đề là không thể trả lời được. Có, đó là một phiên bản của một vấn đề đóng gói. Nhưng hãy xem nghiên cứu của Erich Friedma theo 2 chiều: Có vẻ như vấn đề về hình chữ nhật có kích thước bằng nhau trong hình vuông vẫn chưa được giải quyết - Hãy xem xét sự phức tạp của một số giải pháp này!
http://www2.stetson.edu/~efriedma/squinsqu/
http://www2.stetson.edu/~efriedma/rigidrect/
(Vấn đề được đặt ra hơi khác nhau, tức là làm thế nào để sắp xếp tốt nhất một số lượng nhất định các mặt hàng để chiếm không gian ít nhất, như trái ngược với lựa chọn những mục nào. Nhưng tôi hy vọng vấn đề của bạn làm giảm để lặp loại này tính trong vài sự kết hợp của các đối tượng)
và một 3-d biến thể trông chỉ rất phần giải quyết:. http://www2.stetson.edu/~efriedma/cubincub/
Có lẽ đặt cược tốt nhất của bạn là một heuristic như Anders cho thấy, mặc dù nó gần như chắc chắn sẽ được tối ưu cho hầu hết mọi vấn đề. Điều thú vị là, hầu hết các giải pháp tối ưu dường như có độ cao bất thường, vì vậy có thể bạn sẽ không tìm thấy chúng.
Sự cố Knapsack ở dạng hộp? –
Đó là một trong những vấn đề Maraton Match của TCO, nếu bạn đăng ký tại TCO, bạn có thể tìm thấy một giải pháp tốt cho nó (Tôi không biết chính xác khi nào nhưng tôi nghĩ khoảng một năm trước). không phải của giải pháp là câu trả lời chính xác tất cả họ đều cố gắng sử dụng mô phỏng ủ và sth như thế. –