座位调整

座位调整 2006 年百度之星程序设计大赛初赛题目 5

座位调整

题目描述：

百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

调整的方法如下：

1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

数据输入：

第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

第二行是 N 个整数构成的数列 a ，其中 a[i] 表示第 i 个区域可以容纳的员工数， (1<=a[i]<=M ， a[1]+a[2]+..+a[N]=M) 。

紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

答案输出：

对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

3 3

1 1 1

100 50 25

100 50 25

100 50 25

输出样例

175

数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175


***********************************************************************************************


想了几天，都没有想出个好办法来。尽量的往动态规划上靠还是没有成功。只能用最土的穷举法莱解决了
3 3
1 1 1
100 50 25
50 10 8
50 8 3
至少这个例子能跑通，还有一个限制总座位数必须和员工数目一样多。

代码：
#include 

int area_nr;
int employee_nr;

int *capacity_area;

int **employee_favor;

int seat_nr;
struct seat_info {
        int area_id;
        int employee_id;
        int favor;
};

struct seat_info *seats;

int tmp_employee[100];

int update_empty_employee(int seat_id, int empty_employee_id[100]) {
        int empty_employee_nr;
        int i,j;
        memset(empty_employee_id, 0, sizeof(empty_employee_id));
        memset(tmp_employee, 0, sizeof(tmp_employee));
        for (i=0; i                tmp_employee[seats[i].employee_id] = 1;
        }
        for (i=0, j=0; i                if (tmp_employee[i] == 0) {
                        empty_employee_id[j++] = i;
                }
        }
        empty_employee_nr = j;
        return empty_employee_nr;
}

void func(int seat_id) {
        int empty_employee_id[100];
        int empty_employee_nr;
        if (seat_id == seat_nr-1) {
                empty_employee_nr = update_empty_employee(seat_id, empty_employee_id);
                seats[seat_id].employee_id = empty_employee_id[0];
                seats[seat_id].favor = employee_favor[empty_employee_id[0]][seats[seat_id].area_id];
                int i;
                int sum_favor = 0;
                printf("----------------------------\n");
                for (i=0; i                        printf("seat[%d], area = %d, employee = %d, favor = %d\n", i, seats[i].area_id, seats[i].employee_id, seats[i].favor);
                        sum_favor += seats[i].favor;
                }
                printf("sum favor = %d\n", sum_favor);
                return;
        }

        empty_employee_nr = update_empty_employee(seat_id, empty_employee_id);
        int i;
        for (i=0; i                seats[seat_id].employee_id = empty_employee_id[i];
                seats[seat_id].favor = employee_favor[seats[seat_id].employee_id][seats[seat_id].area_id];
                func(seat_id+1);
        }

}

int main(int argc, char **argv) {

        int i,j;

        printf("input:\n");
        scanf("%d %d", &area_nr, &employee_nr);

        capacity_area = (int *)malloc(sizeof(int) * area_nr);
        for (i=0; i                scanf("%d", &capacity_area[i]);
        }

        employee_favor = (int **)malloc(sizeof(int*) * employee_nr);
        for (i=0; i                employee_favor[i] = (int *)malloc(sizeof(int) * area_nr);
                for (j=0; j                        scanf("%d", &employee_favor[i][j]);
                }
        }

        printf("input success:\n");

        printf("area_nr = %d, employee_nr = %d\n", area_nr, employee_nr);
        printf("area capacity: \n");
        for (i=0; i                printf("%d\t", capacity_area[i]);
        }
        printf("\n");
        printf("employee favor: \n");
        for (i=0; i                printf("[%d] : ", i);
                for (j=0; j                        printf("%d\t", employee_favor[i][j]);
                }
                printf("\n");
        }


        seat_nr = 0;
        for (i=0; i                seat_nr += capacity_area[i];
        }

        seats = (struct seat_info *)malloc(seat_nr * sizeof(struct seat_info*));

        int seat_id = 0;
        for (i=0; i                for (j=0; j                        seats[seat_id].area_id = i;
                        seats[seat_id].employee_id = -1;
                        seats[seat_id].favor = -1;
                        seat_id++;
                }
        }
        func(0);

        return 0;
}