질문은 고전적인 가중치 간격 스케줄링 문제가 있지만 추가 요구 사항이 있습니다. 이 요구 사항은 특정 작업에서 몇 가지 작업을 수행해야합니다.최소 요구 작업 요구 수를 가진 가중치 간격 스케줄링
나는 이미 bruteforce로 해결했다. 하지만 더 효율적인 솔루션이 필요합니다. 동적 프로그래밍과 함께 고전 가중 스케줄링 문제를 해결합니다.하지만이 제약으로 나는 할 수 없습니다. 제안 할 것이 있습니까. 덕분에 조언.
단지 고전 스케줄링 문제 차원 작업의 수를 준다
에 따라 또 하나 개의 차원을 추가 지금까지
예를 들면 완료되었습니다.
가F는 [I]는 [j]가 나는, J 작업이 완료하여, 최대 이익
F [I] [J] F를 결정할 수 무엇 [job_end_time를 [] K] 한번에 수단 [j 개의 + 1] job_start_time [k]> = i
글쎄,이 문제가 기존의 가중치 간격 스케줄링과 얼마나 다른지는 알 수 없습니다. "반드시 수행해야합니다"작업이 겹치지 않는 경우 (그리고 정의가 잘 안된 문제가있는 경우 - 두 개의 겹쳐진 "수행해야하는 작업"중에서 선택하는 방법), 상대적인 가중치를 유지하는 방법이 필요합니다 나머지 일에서.
O (n)에서 작업을 트래버스하고 최대 무게를 찾을 수 있습니다. 그런 다음 "완료해야합니다"작업에 대해 최대 값을 가중치에 추가해야합니다. 이는 상대적인 가중치가 우선 순위가없는 작업보다 확실히 높을 것이므로 다른 직무에 비해 선택 될 수 있습니다.
내가 말했듯이 유일한 문제는 "해야 할 일"이 중복되는 경우입니다. 이 경우에는 선택되지 않은 일부 필수 작업으로 끝납니다 (하나를 선택해야하므로 다른 작업보다 우선해야합니다).
입력은 무엇을 의미합니까? 첫 번째 줄은 ** ** 완료해야 할 일자리 수이고,'2 6 50'은 무엇입니까? – vlad
정보 부족으로 불편을 끼쳐 드려 죄송합니다. 나는 질문을 업데이트한다. – sekogs