알고리즘 분석의 작업 분배 문제

ACM 에서 의 업무 분배 문 제 는 전형 적 인 역 추적 문제 로 역 추적 사상 을 이용 하여 문제 의 해 를 정확하게 얻 을 수 있다.다음은 이 문 제 를 잘 분석 해 보 겠 습 니 다.
질문 설명:
n 개의 업무 가 n 개인 에 게 분배 되 어 있다.제 i 개인 에 게 업무 j 를 분배 하 는 데 필요 한 비용 은 c [i] [j] 이다.하나의 알고리즘 을 시험 적 으로 설계 하여 가장 좋 은 업무 분배 방안 을 계산 하여 모든 사람 에 게 1 개의 서로 다른 업 무 를 분배 하고 총 비용 을 최소 화 시킨다.
문제 풀이 방향:
모든 사람 이 반드시 업 무 를 배정 해 야 하기 때문에 여기 서 2 차원 배열 c [i] [j] 를 만들어 i 호 노동자 가 j 호 업 무 를 완성 하 는 데 필요 한 비용 을 표시 할 수 있다.모든 노동자 가 배 치 될 때 까지 순환 을 정 하고 첫 번 째 노동자 부터 순환 분배 작업 을 시작한다.i 번 째 노동 자 를 위해 업 무 를 배정 할 때 모든 업무 가 이미 분배 되 었 는 지 순환 적 으로 검사 하고 없 으 면 i 번 노동자 에 게 배정 되 며 그렇지 않 으 면 다음 업 무 를 검사 합 니 다.1 차원 배열 x [j] 로 제 j 호 작업 이 할당 되 었 는 지, 할당 되 지 않 으 면 x [j] = 0, 그렇지 않 으 면 x [j] = 1 을 표시 할 수 있 습 니 다.역 추적 사상 을 이용 하여 노동자 순환 이 끝 난 후에 이전 노동자 로 돌아 가 이번 분 배 된 일 을 취소 하고 다음 일 을 분배 할 수 있 을 때 까지 분배 한다.이렇게 해서 첫 번 째 노동자 로 거 슬러 올 라 가면 모든 실행 가능 한 해 를 얻 을 수 있다.업무 분 배 를 검사 할 때 사실은 실행 가능 한 해 를 얻 었 다 고 판단 할 때 2 차원 배열 의 하 표 는 모두 다 르 고 2 하 표 는 똑 같이 다르다.
샘플 분석:
3 가지 업 무 를 정 하고 i 번 노동자 가 j 번 업 무 를 완성 하 는 비용 은 다음 과 같다.
10 2 3
2 3 4
3 4 5
하나의 변수 count 는 작업 비용 의 총 계 를 나타 내 고 초기 에는 0 이 며 변 수 는 i 번 근로 자 를 나타 내 며 초기 에는 1 이다.n 은 총 작업량 을 나타 내 는데 여 기 는 3 을 취한 다.c [i] [j] 는 i 호 노동자 가 j 호 업 무 를 완성 하 는 비용 을 나타 내 고 x [j] 는 j 호 업무 가 분배 되 었 는 지 여 부 를 나타 낸다.알고리즘 은 다음 과 같 습 니 다.

void work(int i,int count){
  if(i>n)
    return ;
  for(int j=1;j<=n;j++)
    if(x[j] == 0){
      x[j] = 1;
      work(i+1,count+c[i][j]);
      x[j] = 0;
    }
}

그렇다면 여기 서 역 추적 법 을 사용 하 는 사상 은 먼저 분 배 된 일 은:
10:c[1][1] 3:c[2][2] 5:c[3][3] count=18;
이때 모든 노동자 의 분배 가 끝 난 후에 두 번 째 노동자 로 거 슬러 올 라 가 재배 치 한다.
10:c[1][1] 4:c[2][3] 4:c[3][2] count=18;
두 번 째 노동 자 는 n 으로 거 슬러 올 라 가 첫 번 째 노동자 의 재배 치 로 거 슬러 올 라 갔다.
2:c[1][2] 2:c[2][1] 5:c[3][3] count=9;
두 번 째 노동자 로 거 슬러 올 라 가 재배 치:
2:c[1][2] 4:c[2][3] 3:c[3][1] count=9;
다시 한 번 첫 번 째 노동자 로 거 슬러 올 라 가 재배 치:
3:c[1][3] 2:c[2][1] 4:c[3][2] count=9;
두 번 째 노동자 로 거 슬러 올 라 가 재배 치:
3:c[1][3] 3:c[2][2] 3:c[3][1] count=9;
이렇게 해서 모든 실행 가능 한 해 를 얻 었 다.한편, 우 리 는 가장 적은 비용, 즉 실행 가능 한 것 과 가장 작은 것 을 받 아야 하기 때문에 전체 변수 cost 를 다시 정의 하여 최종 총 비용 을 표시 해 야 한다. 초기 cost 는 c [i] [i] 의 합, 즉 대각선 비용 을 더 해 야 한다.모든 노동자 가 일 을 분배 할 때 count 와 cost 의 크기 를 비교 합 니 다. count 가 cost 보다 작 으 면 거 슬러 올 라 갈 때 가장 좋 은 해 를 찾 았 다 는 것 을 증명 합 니 다. 이때 count 를 cost 에 부 여 했 습 니 다.
여기까지 전체 알고리즘 은 차이 가 많 지 않 고 곧 끝 날 것 이 며 이미 최종 결 과 를 얻 을 수 있다.그러나 알고리즘 의 복잡 도 를 고려 하여 여기 에는 가지치기 최적화 작업 을 할 수 있다.즉, 국 지적 비용 변수 count 의 값 을 계산 할 때마다 count 가 cost 보다 크다 고 판단 하면 더 이상 분배 할 필요 가 없습니다. 이때 얻 은 해 는 반드시 최 적 화 된 것 이 아 닙 니 다.

#include
using namespace std;

int n,cost=0;
int x[100],c[100][100];

void work(int i,int count){
    if(i>n && count      cost = count;
      return ;
    }
    if(count      for(int j=1;j<=n;j++)
        if(x[j] == 0){  
          x[j] = 1;  
          work(i+1,count+c[i][j]);  
          x[j] = 0;  
         }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        cin>>c[i][j];
        x[j] = 0;  
      }
      cost+=c[i][i];  
    }
    work(1,0);
    cout<    system("pause");
    return 0;
}