Xin chào, tôi đang xây dựng một chương trình trong đó học sinh đang đăng ký một kỳ thi được thực hiện tại một số thành phố trong cả nước. Trong khi đăng ký học sinh cung cấp một danh sách của ba thành phố nơi họ muốn cung cấp cho các kỳ thi theo thứ tự ưu tiên của họ. Vì vậy, một sinh viên có thể nói sở thích đầu tiên của mình cho một trung tâm thi là New York tiếp theo là Chicago tiếp theo là Boston.Thuật toán để giải quyết các vấn đề phân bổ nguồn lực
Bây giờ, hãy nhớ rằng vì các trung tâm thi có khả năng hạn chế nên chúng không thể chứa được mỗi học sinh lựa chọn đầu tiên. cung cấp trung tâm lựa chọn thứ ba cho sinh viên
Bây giờ, bất kỳ ý tưởng nào về thuật toán sắp xếp sẽ làm cho quy trình này trở nên hiệu quả hơn.Đây là cách đơn giản để thực hiện điều này. có thể sau đó đi qua danh sách các lựa chọn thứ hai và phân bổ. Tuy nhiên, điều này có thể dẫn đến những học sinh đầu tiên trong danh sách nhận được trung tâm đầu tiên của họ và các học sinh cuối cùng nhận được sự lựa chọn thứ ba của họ hoặc tệ hơn là không có sự lựa chọn nào của họ. Bất kỳ thứ gì có thể làm cho hiệu quả hơn này
ruột cảm giác của tôi là một thuật toán "hoàn hảo" sẽ là NP-đầy đủ, và bạn sẽ phải giải quyết cho một xấp xỉ. –
Tại sao không chỉ ưu tiên cho những sinh viên đầu tiên đã đăng ký? Bạn phải đánh lừa họ. – alexpirine
Vấn đề là chúng tôi đã được khách hàng đặc biệt yêu cầu không đi với phương pháp tiếp cận đầu tiên đến trước được phục vụ.Lý do là có các sinh viên ở các địa điểm khác nhau có những ngày khác nhau để điền vào mẫu bài kiểm tra của họ. Do đó, không phải lỗi của họ mà họ điền vào mẫu của họ muộn hơn những người khác. – user992010