Có ai biết về Bài toán đóng gói không?

[XSolustion]

Xin cho hỏi về thuật toán đóng gói, hoặc tài liệu nào để thực hiện được!

[Mach2]

hic, mô tả bài toán cụ thể hơn đi :( packing problem hả?

[XSolustion]

Muốn sắp n vật khối có kích thước n(x,y,z) khác nhau vào một hộp có kích thước m(x1,y1,z1). tìm phương án xếp sao cho n vật khối xếp vào khối m nhiều nhất.

[Mach2]

Hi Xsolution,

Bài toán bin-packing là một bài toán optimization thuộc loại IP (integer programing). Bài toán của bạn là packing vật khối nên chỉ là linear chứ ko phải nonlinear problem, tuy nhiên nó cũng là 1 NP-hard problem (bài toán không thể xác định trước thời gian giải). Bin-packing problem có 2 cách giải, approximation và exact. Bạn có 2 chọn lựa, dù là cách nào thì code giải cũng có rất nhiều trên mạng.
Cách chính xác là bạn sẽ model và giải bài toán IP. Cách này thì bạn có thể dùng một thư viện optimization nào đó (như Cplex chẳng hạn) rồi model bài toán và giải thử. Hoặc nếu thích challenging thì có thể viết code giải IP. Cách này đòi hỏi bạn phải có mộ ít kiến thức toán học về bài toán này.
Cách approximation thì tôi ko rõ lắm, tuy nhiên search sơ sơ trên mạng thì thấy cũng nhiều. Tôi có vài người bạn làm về cái này, nếu bạn cần thì tôi sẽ liên lạc hỏi tài liệu, nhưng nói trước là nó nằm ở mức một Master project :D
Còn nếu bạn solve bằng một software kiểu như ILOG thì dễ nhất. Tôi có model cho bài toán này, nếu bạn sử dụng ILOG thì tôi sẽ gửi cho.

[XSolustion]

Cám ơn, vậy xin bạn cho tôi biết một số tài liệu ( ở mức thuật toán, tài liệu luận văn,... ở mức nào củng được).

[Mach2]

Bin-packing 1D chính là bài toán knap-sack cổ điển, tuy nhiên 2D và 3D lại là khác. Tôi đã model thử thì thấy khá phức tạp, nonlinear objective :(
Bạn tham khảo sơ về bài toán bin-packing ở đây.
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/NODE192.HTM
Theo đó thì lời giải tốt nhất cho bài toán (2d, 3d problem,...) này vẫn chưa có, chỉ có lời giải heuristic mà thôi. Các paper liên quan trên đó nếu bạn ko tìm được thì tôi sẽ giúp.