Thuật toán tham lam cho các tài nguyên giới hạn k

Question

Tôi đang nghiên cứu các thuật toán tham lam và tôi tự hỏi giải pháp cho một trường hợp khác.

Đối với vấn đề lựa chọn khoảng thời gian, chúng tôi muốn chọn số hoạt động tối đa không đụng độ với nhau, vì vậy hãy chọn công việc có thời gian hoàn thành sớm nhất.

Ví dụ khác; chúng tôi có n công việc và chúng tôi muốn mua số lượng tài nguyên nhỏ nhất có thể. Ở đây, chúng ta có thể sắp xếp tất cả các công việc từ trái sang phải, và khi chúng ta gặp một điểm khởi đầu mới, chúng ta tăng bộ đếm và khi chúng ta gặp điểm cuối, chúng ta giảm bộ đếm. Vì vậy, giá trị lớn nhất mà chúng tôi nhận được từ bộ đếm này sẽ là số lượng tài nguyên chúng tôi cần mua.

Nhưng ví dụ: nếu chúng ta có n nhiệm vụ nhưng tài nguyên k thì sao? Điều gì sẽ xảy ra nếu chúng ta không có đủ khả năng tài nguyên k? Làm thế nào nên là một giải pháp tham lam để loại bỏ càng ít nhiệm vụ càng tốt để thỏa mãn điều này?

Ngoài ra nếu có tên cụ thể cho vấn đề cuối cùng tôi đã viết, tôi rất vui khi biết điều đó.

Answer 1

Điều này giống như trường hợp chung của phiên bản mà chúng tôi chỉ có một tài nguyên.

Bằng trực giác, bạn nên sắp xếp công việc theo thời gian kết thúc và thực hiện từng bước một theo thứ tự đó. Bây giờ, thay vì kết thúc thời gian của công việc cuối cùng, chúng tôi theo dõi thời gian kết thúc của các công việc k cuối cùng được chấp nhận vào tài nguyên của chúng tôi. Đối với mỗi công việc, chúng tôi kiểm tra xem các công việc hiện tại bắt đầu thời gian có lớn hơn công việc cuối cùng trong bất kỳ tài nguyên nào của chúng tôi hay không. Nếu không tìm thấy tài nguyên như vậy, chúng tôi sẽ bỏ qua công việc đó và tiến lên phía trước. Nếu tìm thấy một tài nguyên, chúng tôi chỉ định công việc đó cho tài nguyên đó và cập nhật thời gian kết thúc. Nếu có nhiều hơn một tài nguyên có thể thực hiện công việc đó, bạn nên gán nó cho tài nguyên với thời gian kết thúc mới nhất.

Tôi không thực sự có bằng chứng về chiến lược tham lam này, vì vậy nó cũng có thể sai. Nhưng tôi không thể nghĩ ra một trường hợp mà việc thay đổi lựa chọn có thể cho phép chúng tôi phù hợp với nhiều công việc hơn.