Bài toán phân công công việc

[Nguyen_Minh_Chi (Nguyễn Minh Chí)]

Đề bài là:

Em chỉ mới nghĩ ra cách sử dụng thuật toán tham lam là biểu diễn ABCD bằng 1 mảng 24 phần tử (tương ứng 24h) gồm 0 (giờ không thể trực) và 1 (giờ có thể trực), sau đó ví dụ thời gian cần giám sát là từ 10 -> 15 thì duyệt ABCD chọn ra ai có số lượng phần tử bằng 1 trong index từ 10 -> 15 lớn nhất thì chọn (ở ví dụ là A [12,13,14,15] =1 và mảng 10-> 15 còn 10 11 là chưa ai trực) sau đó tiếp tục duyệt như trên đến khi mảng giờ trực hết thì dừng lại .
Mọi người có cách nào xử lý hay hơn không ạ, em mới học thuật toán nên toàn sử dụng tham lam là nhiều
Cảm ơn mọi người nhiều ạ

[Stanley00 (Stanley)]

Vẫn biểu diễn bài toán như này:

Em chỉ mới nghĩ ra cách sử dụng thuật toán tham lam là biểu diễn ABCD bằng 1 mảng 24 phần tử (tương ứng 24h) gồm 0 (giờ không thể trực) và 1 (giờ có thể trực). Giờ cần trực là mảng T, với giá trị 1 là cần trực

Nhưng tiêu chí tham lam để chọn thì nên đổi lại chút xíu:

1. Đầu tiên, xác định xem có thể bố trí người được hay không: với mỗi giờ cần trực, đều có ít nhất 1 người rảnh: OR(A, B, C, D) AND T == T. Không thỏa => return luôn
2. Xét những giờ nào chỉ có 1 người có thể trực: chắc chắn phải chọn người đó
3. Với những giờ có được nhiều người trực: ưu tiên chọn những người đã chọn trước đó ở bước 2 hoặc 3

[rogp10]

Bài này (minimum set cover) cấp NP-hard rồi nên chỉ có thể greedy thôi.

[bttrthnysrdy (phạm thị vân)]

bác ơi cho em xin cả đề được không ạ