#include <iostream.h>

/*
文件描述：解百度赛题第五题
创建人：  陈泽丹
版本号：  1.0
修改次数：0

补充： 我是在以比赛时间(8小时)试练自已, 含这题内8小时6道题里我只做出了三道(2,5,6),这题十分遗憾，规定时间内想不出用动态规划提高效率的办法。但既然时限已快完了,"交卷"喽...
*/

const int N_Max=3000;
const int M_Max=300;
int capacity[N_Max];
int interest[M_Max][N_Max];

void Init(int M, int N)
{
    cout<<"请输入各个区域的容纳量:"<<endl;
    for (int area=0; area<N; area++)
    {    
        cin>>capacity[area];
    }
    for (int i=0; i<M; i++)
    {
        cout<<"请输入员工"<<i+1<<"各个区域的喜好度:"<<endl;
        for (int j=0; j<N; j++)
        {
            cin>>interest[i][j];
        }
    }
}

int fun(int i, int M, int N)
{
    if (i<M)
    {
        int j, max, t;
        for (j=0, max=0; j<N; j++)
        {
            if(capacity[j] > 0)
            {
                capacity[j]--;
                t=fun(i+1,M, N)+interest[i][j];
                if(t > max ) max=t;
                capacity[j]++;
            }
        }
        return max;
    }
    return 0;
}

void main()
{
    int m, n;
    cout<<"请输入区域数，员工数:"<<endl;
    cin>>n;
    cin>>m;
    Init(m,n);
    cout<<fun(0,m,n)<<endl;
}

liyanhonghenniua,woyaoqubaidu!

/*
算法介绍：
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个员工总的最大喜好度
}

有简单的方法

???
愿闻其详,也引用一下论坛的时髦语,求救啊,sos...

...有好东西就交流下,不要藏私嘛...再说了,这世上高手太多啦,藏私那些高手也不会因不知道就永远解不了,相反却停止了自已前进的步履和验证的功能...嘻,怎么样?要不,今晚面条算我的?...呵呵

写了个很长的...
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;

struct Employee
{
    vector<int> arealike;
};

struct Area
{
    Area(const vector<Employee> &_employees)
        :employees(_employees), totallike(0), rest(0)
    {
    }
    int rest;
    vector<int> employeelist;
    const vector<Employee> &employees;
    int index;
    int totallike;
    struct sort_employee_by
    {
        const vector<Employee> &employees;
        const int index;
        sort_employee_by(const vector<Employee> &_employees, int _index)
            :employees(_employees), index(_index)
        {
        }
        bool operator() (const int a, const int b)
        {
            return employees[a].arealike[index] < employees[b].arealike[index];
        }
    };
    int getnextdiff() const
    {
        if (rest == 0)
            return -2;
        int size = employeelist.size();
        if (size == 0)
            return -1;
        if (size == 1)
            return employees[size - 1].arealike[index];
        return employees[size - 1].arealike[index] - employees[size - 2].arealike[index];
    }
    void remove(int i)
    {
        vector<int>::iterator it = find(employeelist.begin(), employeelist.end(), i);
        if (it != employeelist.end())
        {
            employeelist.erase(it);
        }
    }
    int pick()
    {
        assert(rest > 0);
        rest--;
        int e = employeelist.back();
        totallike += employees[e].arealike[index];
        return e;
    }
};

bool sort_area(const Area * const a, const Area * const b)
{
    return a->getnextdiff() > b->getnextdiff();
}
int main(int argc, char **argv)
{
    int n, m, i, j;
    freopen(argv[1], "r", stdin);
    scanf("%d%d", &n, &m);
    vector<Employee> employees(m, Employee());
    vector<Area> areas(n, Area(employees));
    vector<Area*> areaps(n, (Area*)NULL);
    for (i = 0; i < n; i++)
    {
        areas[i].index = i;
        areaps[i] = &areas[i];
        areas[i].employeelist.insert(areas[i].employeelist.begin(), m, 0);
        for (j = 0; j < m; j++)
        {
            areas[i].employeelist[j] = j;
        }
        scanf("%d", &areas[i].rest);
    }
    for (j = 0; j < m; j++)
    {
        Employee &e = employees[j];
        e.arealike.insert(e.arealike.begin(), n, 0);
        for (i = 0; i < n; i++)
        {
            e.arealike.push_back(0);
            scanf("%d", &e.arealike[i]);
        }
    }
    for (i = 0; i < n; i++)
    {
        sort(areas[i].employeelist.begin(), areas[i].employeelist.end(), Area::sort_employee_by(employees, i));
    }
    int totallike = 0;
    while(!areaps.empty())
    {
        sort(areaps.begin(), areaps.end(), sort_area);
        while(!areaps.empty() && areaps.back()->rest == 0)
        {
            totallike += areaps.back()->totallike;
            areaps.pop_back();
        }
        if (areaps.empty())
            break;
        int e = areaps[0]->pick();
        for (i = 0; i < n; i++)
        {
            areas[i].remove(e);
        }
    }
    printf("%d\n", totallike);
    return 0;
}

省略读取文件部分

bool CSeat::swap(int z1,int z2)
{
    bool flag = false;
    int sum1,sum2;
    int n1 = zones[z1].num;
    int n2 = zones[z2].num;
    int i,j;
    for(i=0;i<n1;i++)
        for(j=0;j<n2;j++){
            sum1 = p[zones[z1].employee[i]][z1] + p[zones[z2].employee[j]][z2];
            sum2 = p[zones[z1].employee[i]][z2] + p[zones[z2].employee[j]][z1];
            if(sum2>sum1){
                int temp = zones[z1].employee[i];
                zones[z1].employee[i] = zones[z2].employee[j];
                zones[z2].employee[j] = temp;
                max += sum2 - sum1;
                flag = true;
            }
        }
    return flag;
}

void CSeat::swapall()
{
    int i,j;
    bool flag = true;
    while(flag){
        flag = false;
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                flag = swap(i,j);
    }
    cout<<max<<endl;
}

想了一个方法,没有写代码,

对每个地方一一进行安排,每次都选最大的那几个数,如果该人已经被安排了,就试一下该人到底安排在哪个地方好,每次都往好的情况调整.

上面两位的回溯应该会TLE吧

[quote]想了一个方法,没有写代码,

对每个地方一一进行安排,每次都选最大的那几个数,如果该人已经被安排了,就试一下该人到底安排在哪个地方好,每次都往好的情况调整.

上面两位的回溯应该会TLE吧[/quote]

这种方法我做过对比的程序,是错误的。
实际上，这种方法只考虑局部最优,但局部最优不等于全局最优.

楼上举个数据先