Bài toán xếp hình hộp chữ nhật nhỏ vào trong hình hộp chữ nhật lớn

[Minh2 (Minh)]

Em có 1 bài toán sau mà nghĩ mãi chưa ra cách làm, nhờ anh/chị gợi ý hướng giải.

Input: đọc từ file

• Dòng 1: X Y Z
  • X: chiều dài của hình hộp chữ nhật lớn
  • Y: chiều rộng của hình hộp chữ nhật lớn
  • Z: chiều cao của hình hộp chữ nhật lớn
• Dòng 2: N
  • N: số lượng loại hộp nhỏ
• N dòng tiếp theo, tương ứng từng loại hộp nhỏ có x, y, z, n và gt:
  • x: chiều dài hình hộp nhỏ
  • y: chiều rộng hình hộp nhỏ
  • z: chiều cao hình hộp nhỏ
  • n: số lượng của loại
  • gt: giá trị của loại

Output: Tọa độ xếp các hình nhỏ vào hình lớn sao cho giá trị thu được là lớn nhất.

[Red_Sand (mondlicht1)]

Gọi hàm xếp các khối vào là fit(small box, space). Hàm fit không chỉ áp dụng với hình hộp chữ nhật mà áp dụng chung cho cả khối không gian khả dụng. fit phải ưu tiên đặt small box sao cho space còn lại dư ra khối chữ nhật lớn nhất. Thử fit() với tất cả box còn lại như phương pháp brute_force, nhưng lưu kết quả tốt nhất để tái sử dụng cho lần thử kế, hay còn gọi là quy hoạch động.