Greedy 예제(3) Two City Scheduling

 

예제3) 도시 A,B가 있다. 한 회사에서 직원 6명을 도시 A, B 각각 3명씩 출장 보낼 때 최소 비용을 구하라.

 

 

A 도시와 B 도시에 직원을 할당 할 때, 어떤 직원을 우선적으로 할당해야 할까? 답 : A와 B 비용의 차이가 큰 직원

 

사람6의 경우 A도시를 가든, B 도시를 가든 100의 비용이 든다. 

사람4의 경우 A도시를 가면 10의 비용이 들고 B 도시를 가면 100의 비용이 든다. 사람4를 A도시로 보내면 90을 절약할 수 있다. 

 

절약할 수 있는 비용이 큰 직원부터 도시를 할당해야 된다. ( Greedy 알고리즘 )

 

 

알고리즘

 

1) 비용의 차이를 기준으로 정렬한다. 

 

 

2) 0부터 2까지는 B도시에 할당하고 3부터 5까지는 A도시에 할당한다. 

 

 

---

 

참고영상