Help:Bài toán thực tế Mình có một bài toán như sau: Cho trước hình chữ nhật kích thước axb, hình tròn có bán kính R. Yêu cầu của bài toán: Sắp xếp trên 1 hình cho trước (đơn giản như hình chữ nhật, phức tạp thì hình bất kì (cái này chắc khó) ) các hình chữ nhật, và hình tròn trên sao cho: (tổng diện tích các hình chữ nhật + các hình tròn) / diện tích hình cho trước đạt giá trị max Giúp mình hướng giải quyết bài này nhé, cám ơn các bạn[
Theo mình thấy đây là một bài toán không hề đơn giản. Có thể phát biểu lại bài toán như sau: Cho trước không giới hạn các hình chữ nhật a*b và các hình tròn bán kính R. Giả sử ta có một "hình kín" H nào đó, hãy sắp xếp các hình tròn và hình chữ nhật trên vào hình H sao cho các hình đó không chồng lên nhau và tổng diện tích là lớn nhất. ---------------------------------------- Về mặt tổng quát thì mình nghĩ không có lời giải tổng quát cho bài toán trên. Tuy nhiên nếu thay hình H tổng quát bằng một hình chữ nhật AxB thì bài toán có thể giải được, nhưng nếu giải được thì lời giải cũng khá phức tạp và rườm rà vì có lẽ có nhiều trường hợp. Bài toán này cũng có thể xét trường hợp H là hình vuông, tròn tam giác,..., nào đó. @chủ topic: mình nghĩ trừ phi người đã tiếp xúc với những vấn đề tương tự, còn không e rằng ít có người chịu bỏ thời gian ra để giải quyết cho bạn vấn đề này! Được meofmaths sửa chữa / chuyển vào 17:06 ngày 07/11/2007
Cám ơn bạn,mình đang làm bài tập lớn về toán rời rạc không ngờ bốc vào cái để khó thế này. Mình cũng nghĩ trong truờng hợp tổng quát bài toán này không có lời giải, nhưng nếu hình cho trước là hình chữ nhật( tam giác,tròn) thì sẽ có lời giải. Đây là bài toán tối ưu mình nghĩ chắc đã có nhiều người nghĩ về bài toán này rồi, ví dụ như cắt trên tấm vải hoặc tấm da hình chữ nhật chẳng hạn, cắt làm sao ít lãng phí nhất. Đầu tiên mình nghĩ là nó ko khó lắm nhưng ko ngờ nó lại khó như thế này. Cả trường hợp đơn giản nhất cũng khó, kiểu này die là chắc. Được lethang85 sửa chữa / chuyển vào 18:52 ngày 07/11/2007
@altus - Cảm ơn bạn Mình đã search trên google những từ khóa mà bạn bảo nhưng có nhiều trang ko cho down về, bài toán của mình lại liên quan đến tối ưu trong tọa độ 2 chiều nên khi search các từ khóa trên có nhiều tài liệu ko đúng với phần mình tìm. Nếu bạn có tài liệu bạn có thể gửi cho mình được ko, thanks!
