N개의 팀의 사람수 목록을 구한다. N[0]=3 N[1]=12 ... 생긴 목록을 L이라고 한다.(L은 연관배열)
L을 사람수의 내림차순으로 정렬한다. N[1]=12 N[0]=3 ...
이제 팀을 버스에 태우는데, L의 순서대로 팀을 버스에 태운다 순서대로 각 버스에 한팀씩 순서대로 태운다. L[0]->B[0] L[1]->B[2] L[3]->B[3] L[4]->B[0] L[5]->B[2]
이렇게 계속하다가 사람의 수가 넘치는 경우가 생긴다. 그러면 그 버스의 다음 버스에 해당 팀을 태운다. 모든 버스를 체크했지만 해당 팀이 들어갈 수 없을 경우 해당팀을 잘라서 처리한다. 하지만 사람수로 내림차순 정리하였기 때문에 이럴 가능성이 적어진다. L의 후반부의 팀들은 사람수가 적기 때문에 좀더 유연하게 버스 선택이 가능하다.
예
N = [20,3,2,30,10,8,8,12,9,9,8,7] 총 인원 126명 필요 버스수 = ceil(126/45) = 3대
B = array(45,45,45); // 버스 123호 각각 45명의 자리
L = [30,20,12,10,9,9,8,8,8,7,3,2] //사람수로 내림차순 정렬
분배 알고리즘 동작
버스1호에 30명이 탈 수 있다. B=[15,45,45]
버스2호에 20명이 탈 수 있다. B=[15,25,45]
버스3호에 12명이 탈 수 있다. B=[15,25,33]
버스1호에 10명이 탈 수 있다. B=[05,25,33]
버스2호에 09명이 탈 수 있다. B=[05,14,33]
버스3호에 09명이 탈 수 있다. B=[05,14,24]
버스1호에 08명이 탈 수 없다. B=[05,14,24] SKIP!
버스2호에 08명이 탈 수 있다. B=[05,06,24]
버스3호에 08명이 탈 수 있다. B=[05,06,16]
버스1호에 08명이 탈 수 있다. B=[05,06,16] SKIP!
버스2호에 08명이 탈 수 있다. B=[05,06,16] SKIP!
버스3호에 08명이 탈 수 있다. B=[05,06,08]
버스1호에 07명이 탈 수 있다. B=[05,06,08] SKIP!
버스2호에 07명이 탈 수 있다. B=[05,06,08] SKIP!
버스3호에 07명이 탈 수 있다. B=[05,06,01]
버스1호에 03명이 탈 수 있다. B=[02,06,01]
버스2호에 02명이 탈 수 있다. B=[02,04,01]
END
추가
버스를 순서대로 돌리지 않고 그때 가장 자리가 많은 버스에 손님을 태우는 쪽이 더 효율적일 것 같다.
분배 알고리즘 동작
[버스1호] 30명이 탈 수 있다. B=[15,45,45]
[버스2호] 20명이 탈 수 있다. B=[15,25,45]
[버스3호] 12명이 탈 수 있다. B=[15,25,33]
[버스3호] 10명이 탈 수 있다. B=[15,25,23]
[버스2호] 09명이 탈 수 있다. B=[15,16,23]
[버스3호] 09명이 탈 수 있다. B=[15,16,14]
[버스2호] 08명이 탈 수 있다. B=[15,08,14]
[버스1호] 08명이 탈 수 있다. B=[07,08,14]
[버스3호] 08명이 탈 수 있다. B=[07,08,06]
[버스2호] 07명이 탈 수 있다. B=[07,01,06]
[버스1호] 03명이 탈 수 있다. B=[04,01,06]
[버스3호] 03명이 탈 수 있다. B=[04,01,02]
END
코드로
N = array([~~~~~~~~~~~~~~~~]);
N_total = array_sum(N);//총 사람수
L = arsort(N); //php에서는 본래 반환값이 없지만 그냥.. 보기 쉽도록)
B = array();
for(i=0,m=ceil(N_total/45);i<m;i++){
B[]=45; //45명 탈 수 있는 버스를 추가
}
for(i=0,m=count(L);i<m;i++){
arsort(B);
temp_B = B[0]; //최고로 자리가 많은 버스의 자리수
if(temp_B>L[i]){
B[0]-=L[i];
}else{
countinue; //이 팀은 하나의 버스에 탈 수 없다.//에러 배열에 넣고 나중에 예외처리를 한다.
