나는 다음과 같은 조건의 문제를 해결하는 알고리즘을 필요로

Question

사용할 알고리즘을 파악하는 데 도움이 필요 :

는 "N"사람들의 세트와 "M"워크숍의 또 다른 세트가, 더있다 사람들은 워크샵보다. 각 개인은 전체 워크샵 중 "j"크기의 하위 집합을 선택하고 해당 워크샵을 얼마나 돕고 싶은지에 따라 각각에 값을 할당했습니다. 현재, 모든 워크숍에는 제한된 금액의 공석 만 있습니다. 이러한 조건을 감안할 때

는

문제는 다음과 같습니다

, 즉 경우에, 어떤 (문제의 제약 주어진 각 사람이 그녀가 가장 중요한 고려 워크숍에 참여하도록, 워크샵 명을 할당하는 가장 좋은 방법입니다

사람이 첫 번째 선택에 참여할 수없는 경우 알고리즘은 두 번째, 세 번째, 네 번째 등을 선택해야합니다.

나는이 문제가 조합 최적화와 관련이 있다고 생각하지만 알고리즘에 대해서는 많이 모른다. 누구든지 조사를 시작할 이름을 누군가에게 말해 줄 수 있다면 매우 감사 할 것입니다.

감사합니다. 그리고 내 영어를 용서해주십시오.

Answer 1

이것은 일방적 인 선호도 (사람들이 워크샵에 대한 선호도를 가졌지 만 그 반대의 경우는 아님)와 일치하는 문제입니다. https://mattmccutchen.net/lumc/index.html

이 문제에 대한 최적해가 특히 명확하지 않다 :

여기에이 문제에 대한 자세한 내용 우수한 종이이다. 다양한 최적 (파레토 효율적) 기준이 있습니다. 불행히도이 문제는 많은 사람들에게 NP 하드가 아닙니다.

그러나 다항식 시간 알고리즘의 기준이 있습니다. 내가 링크 한 논문의 "관련 저작물"섹션에 이것들의 좋은 목록이 있습니다.