算法习题——工作分配问题

问题描述:

有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。 设计一个算法，对于给定的工作费用，为每一个人都分配1 件不同的工作，并使总费用达到最小。

解题思路：

使用回溯法排列树找到每一个解向量x，
其中i代表第i个工人，x[i]代表第i个工人分配的工作。
这样在每次找到一个解向量后，就可以计算出其费用，然后通过一个变量就可以迭代出最小的费用。在排列树的寻找过程中没有约束条件。
输入：

3
10 2 3
2 3 4
3 4 5

输出：

9

代码：

#include <stdio.h>
//表示输入的工人个数或者工作个数
int n;
//通过排列树得到的解向量计算每次的开销
int cost = 0;
//得到cost后与之比较，保证得到的是最小值
int prev = 99999999;
//i代表第i个工人，x[i]代表第i个工人分配的工作。
int x[100];
//存放将工作i分配给第j个人所需的费用
int list[100][100] = {0};

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void backTrack(int t) {
    if (t > n) {
        
        for(int i = 1; i <= n; i++){
            cost += list[i][x[i]];
        }

        if (cost < prev) {
            prev = cost;
        }
        cost = 0;
        
    }

    else {

        for (int i = t; i <= n; i++) {
            swap(&x[i], &x[t]);
            backTrack(t+1);
            swap(&x[i], &x[t]);
        }

    }
}

int main(void) {
    scanf("%d", &n);

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            scanf("%d", &list[i][j]);
        }
    }


    for(int i = 1; i <= n; i++) {
        x[i] = i;
    }

    backTrack(1);
    printf("%d\n", prev);
}