Bài toán xếp đồ vào thùng đồ

[Zteam]

như tít , mình đang mò làm cái game cho vui thì gặp 1 bài toán thế này
cho 1 thùng đồ có kích thước mn , và các món đồ có kích thước xác định xy , viết thuật toán để xếp các món đồ vào thùng đồ sao cho

1. các món đồ ko được chồng lên nhau
2. tiết kiệm được diện tích là tối đa

đầu ra cần biết là tọa độ có thể đặt món đồ
đầu vào là kích thước thùng đồ , kích thước vật

hiện giờ mình cũng đã viết tạm 1 cách để đặt món đồ vào thùng đồ nhưng củ chuối quá

vd: đặt 1 món đồ có kích thước 2x2 vào vị trí đầu tiên của thùng đồ ta cần tính được tọa độ vị trí của món đồ sẽ đặt vào , ở đây vị trí đầu tiên sẽ là 0 , món đồ tiếp theo có kích thước 2x3 thì chỉ có thể đặt ở các vị trí khác tọa độ 0,1 , 8 , 9 ( ở đây tọa độ đánh số bắt đầu từ ô đầu tiên là 0 , tiếp sau là 1,2… , hàng tiếp theo là 8,9…)

[SITUVN.gcd]

Nếu theo hình trên thì thuật toán của bạn có lưu vị trí của món đồ được đặt cuối cùng hoặc (x, y) lớn nhất.
Mỗi lần đặt vào là phải duyệt từ (0, 0) chứ nhỉ.

[Zteam]

ý anh là phải lưu tất cả các tọa độ đã được đặt chỗ vào 1 mảng 2 chiều , rồi sau này khi muốn đặt 1 món đồ nào đó thì mình vào mảng đó tìm vị trí trống phù hợp để đặt món đồ tiếp theo à ?

hiện tại em làm theo cách rất củ chuối là ko tạo 1 mảng như vậy mà chỉ xét vị trí của món đồ cuối cùng được đặt vào , và em lấy chiều cao lớn nhất của món đồ trong cùng 1 hàng , mỗi món đồ được xếp vào tuần tự theo từng hàng , hết hàng trên thì sẽ xuống hàng dưới

[nitro2 (Nhím)]

Mình rất thích các dạng bài toán có ứng dụng thực tế cao như ví dụ của bạn.
Mình có thể đề xuất 2 giải thuật dựa trên những giả định sau:

• Theo mình quan sát thấy, các khối đồ của bạn chỉ có dạng hình vuông hoặc chữ nhật, kích thước 1x1, 1x2, 1x3, 1x4, 2x2, 2x3, 2x4.
• Vật dụng không thể xoay chiều

Cấu trúc dữ liệu:

• Thùng chứa đồ là một mảng 2 chiều có kích thước m*n (default m = 8 và chia hết cho 2).
• Giá trị của mỗi phần tử trong mảng là ID của item. Vị trí trống có giá trị 0.
  
• Mỗi item sẽ có 4 thông số: ID, Position (x,y) , Width and Height.

Giải thuật 1 - Lấp đầy:

• Lần lượt chạy quét từ vị trí (0,0) tới vị trí cuối cùng của mảng. Nếu vị trí đó trống thì check điều kiện xem các ô phía dưới tương ứng với cạnh và cột có trống không (có bằng 0 hay không). Cụ thể mã giả: for (x,y) in array[m][n]: return (x,y) if checkValidXY(x,y, width, height) else continue. Chú ý trường hợp thùng đồ đầy.
• Ưu điểm: Đơn giản và hiệu quả với đa số trường hợp.
• Nhược điểm: Có thể có lỗ trống. Nhưng theo đánh giá của mình là không thành vấn đề vì các item nhỏ sẽ lấp đầy lỗ trống khi có item mới.

Giải thuật 2 - Ghép cụm:

• Mình để ý thấy các item của bạn đa số có kích thước là 2 x h hoặc w x 2 (Chia hết cho 2).
  Mục tiêu của giải thuật này là lấy kích thước 2x4 làm chuẩn, tạm gọi là 1 sector.
• Mỗi khi có item mới, thì thử ướm nó vào sector xem vừa không, không vừa thì tiếp tục với sector tiếp theo. Như vậy ta có thể có các sector như (2x2 + 2x2), (2x4), (2x3 in 2x4), (2x2 + 1x2 + 1x2) .
  

[Zteam]

thanks bạn mình làm đc rồi