/*
  Name:
  Copyright:
  Author:
  Date: 28-05-06 15:26
  Description: 5.座位调整
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现,员工如果可以在自己喜欢的美食旁边工作,效率会大大提高。因此,百度决定进行一次员工座位的大调整。

调整的方法如下:
1.首先将办公区按照各种零食的摆放分成N个不同的区域(例如:可乐区,饼干区,牛奶区等等);
2.每个员工对不同的零食区域有不同的喜好程度(喜好程度是1~100的整数, 喜好程度越大表示该员工越希望被调整到相应的零食区域);
3.由于每个零食区域可以容纳的员工数量有限,人力资源部希望找到一个最优的调整方案使得总的喜好程度最大。


输入要求:
文件第一行包含两个整数N,M(N>=1,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


评分规则:
1.程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试用例上运行不能超过10秒,否则该用例不得分;
2.要求程序能按照输入样例的格式读取数据文件,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;
3.该题目共有4个测试用例,每个测试用例为一个输入文件。各测试用例占该题目分数的比例分别为25%,25%,25%,25%;
4.该题目20分。

*/
/*
算法介绍:
1。读入数据N,M,a[]和p[][]。
2。以员工为主序,采用回溯的方法依次处理每一个员工在每个位置的喜好程度,返回总的最大的喜好程度。
*/

#include <iostream>
#include<fstream>
#include <time.h>

using namespace std;

const int MAX = 301;
void Readata(const char *filename, int a[], int p[][MAX], int & N, int & M);
int GetPlace(int N, int maxMen, int man, const int p[][MAX], int a[]);

int main()
{
 time_t startTime;
 time_t endTime;
 time(&startTime);

      int N, M;
      int a[MAX] = {0};
      int p[MAX][MAX] = {0};

 Readata("in5.txt", a, p, N, M);//读入数据

// cout << M << ' ' << N << endl;
// for (int i=1; i<=N; i++)
//            cout << a[i] << ' ';
//      cout << endl;
//      for (int i=1; i<=M; i++)
//      {
//            for (int j=1; j<=N; j++)
//                  cout << p[i][j] << ' ';
//            cout << endl;
//      }

      int sum = GetPlace(N, M, 1, p, a);//返回总的最大的喜好程度。
      cout << sum << endl;

 time(&endTime);
 cout << difftime(endTime, startTime) << endl;

 getchar();
 return 0;
}

void Readata(const char *filename, int a[], int p[][MAX], int & N, int & M)
{
      fstream in(filename);
      if (!in)
            return ;   //结束程序执行

      while (!in.eof())
      {
            in >> N;
            in >> M;
            for (int i=1; i<=N; i++)
                  in >> a[i];
            for (int i=1; i<=M; i++)
                  for (int j=1; j<=N; j++)
                        in >> p[i][j];
      }

    in.close(); //关闭文件
}

int GetPlace(int N, int maxMen, int man, const int p[][MAX], int a[])
{
      int max = 0;
      int sum = 0;

      if (man == maxMen)//处理最后一个员工
      {
            for (int i=1; i<=N; i++)
            {
                  if (a[i] > 0)//如果该位置还可以容纳此员工,用sum记录其在该处的喜好度
                        sum = p[man][i];
                  if (sum > max)
                        max = sum;//用max记录该员工可以获得的最大喜好度
            }
      }
      else //如果处理的不是最后一个员工,应采用回溯方法以取得最优解
      {
            for (int i=1; i<=N; i++)
            {
                  if (a[i] > 0)//如果该位置还可以容纳此员工,用sum记录其在该处的喜好度
                  {
                        a[i]--;//该位置可容纳员工数减1
                        sum = p[man][i] + GetPlace(N, maxMen, man+1, p, a);
                        a[i]++;
                  }
                  if (sum > max)
                        max = sum;
            }
      }
      return max; //返回第man到M个员工总的最大喜好度
}

 

Posted on 2006-05-30 13:58 梦想飞扬 阅读(1213) 评论(4)  编辑 收藏 引用

Feedback

# re: 我解百度之星题目之" 座位调整 "  回复  更多评论   

2006-06-13 19:58 by Jacky
拜读了你的算法,能实现题目的要求。你的算法就是把每种可能的情况都遍历一遍,从中得到最大喜好度。但觉得回溯法在这里使用的不太恰当,算法里面并没有回溯的必要,你是把每种情况的最大喜好度算出来后通过比较才确定最大喜好度的。个人认为本题采用动态规划法更好。采用回溯法也可以,但最好写一个判断当前情况下能得到的最大喜好度的函数,然后和当前的最大喜好度进行比较,如果小于当前最大喜好度,就没有必要再递归下去了。

以上看法属个人意见,有错误或疏漏的地方请多指教!谢谢!

# re: 我解百度之星题目之" 座位调整 "  回复  更多评论   

2009-05-13 00:58 by kekedou
这样通过全排列的方法在时间复杂度上太大了吧。。。。有没有更好的方法?

# re: 我解百度之星题目之" 座位调整 "  回复  更多评论   

2009-06-15 23:51 by kuramawzw
网络流或二分图最佳匹配

# re: 我解百度之星题目之" 座位调整 "  回复  更多评论   

2012-11-27 00:06 by 无知者
难道我理解错了

这好像是错的

这样实际判断 最后一个人 选择哪个区域兴趣多
就去哪个区域了
在这里 就已经是错的了

递归+返回值 视乎不能达到对 所有 配对方法的 遍历
需要一个内存区来存放结果

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理