Chinaunix首页 | 论坛 | 博客
  • 博客访问: 24188
  • 博文数量: 6
  • 博客积分: 145
  • 博客等级: 入伍新兵
  • 技术积分: 72
  • 用 户 组: 普通用户
  • 注册时间: 2011-12-20 18:44
文章分类

全部博文(6)

文章存档

2012年(2)

2011年(4)

我的朋友

分类: C/C++

2011-12-31 15:27:28

座位调整 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;
}








阅读(1109) | 评论(0) | 转发(0) |
0

上一篇:个人感言

下一篇:剪刀石头布

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册