/*
? Name:
? Copyright:
? Author:
? Date: 28-05-06 15:26
? Description: 5.座位調(diào)整
百度辦公區(qū)里到處擺放著各種各樣的零食。百度人力資源部的調(diào)研發(fā)現(xiàn)，員工如果可以在自己喜歡的美食旁邊工作，效率會大大提高。因此，百度決定進(jìn)行一次員工座位的大調(diào)整。
調(diào)整的方法如下：
1．首先將辦公區(qū)按照各種零食的擺放分成N個不同的區(qū)域（例如：可樂區(qū)，餅干區(qū)，牛奶區(qū)等等）；
2．每個員工對不同的零食區(qū)域有不同的喜好程度（喜好程度是1~100的整數(shù)， 喜好程度越大表示該員工越希望被調(diào)整到相應(yīng)的零食區(qū)域）；
3．由于每個零食區(qū)域可以容納的員工數(shù)量有限，人力資源部希望找到一個最優(yōu)的調(diào)整方案使得總的喜好程度最大。
輸入要求：
文件第一行包含兩個整數(shù)N，M(N>=1，M<=300)。分別表示N個區(qū)域和M個員工；
第二行是N個整數(shù)構(gòu)成的數(shù)列a，其中a[i]表示第i個區(qū)域可以容納的員工數(shù)(1<=a[i]<=M，a[1]+a[2]+...+a[N]=M)；
緊接著是一個M*N的矩陣P，P(i,j)表示第i個員工對第j個區(qū)域的喜好程度。例：
3 3
1 1 1
100 50 25
100 50 25
100 50 25
輸出要求：
對于每個測試數(shù)據(jù)，輸出可以達(dá)到的最大的喜好程度。例：
175
?
數(shù)據(jù)解釋：
此數(shù)據(jù)只存在一種安排方法，三個員工分別安置在三個區(qū)域。最終的喜好程度為100+50+25=175
評分規(guī)則：
1．程序?qū)⑦\行在一臺Linux機(jī)器上（內(nèi)存使用不作嚴(yán)格限制），在每一測試用例上運行不能超過10秒，否則該用例不得分；
2．要求程序能按照輸入樣例的格式讀取數(shù)據(jù)文件，按照輸出樣例的格式將運行結(jié)果輸出到標(biāo)準(zhǔn)輸出上。如果不能正確讀入數(shù)據(jù)和輸出數(shù)據(jù)，該題將不得分；
3．該題目共有4個測試用例，每個測試用例為一個輸入文件。各測試用例占該題目分?jǐn)?shù)的比例分別為25%，25%，25%，25%；
4．該題目20分。
*/
/*
算法介紹：
1。讀入數(shù)據(jù)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);//讀入數(shù)據(jù)
//?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 ;?? //結(jié)束程序執(zhí)行
????? 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(); //關(guān)閉文件
}
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 //如果處理的不是最后一個員工，應(yīng)采用回溯方法以取得最優(yōu)解
????? {
??????????? for (int i=1; i<=N; i++)
??????????? {
????????????????? if (a[i] > 0)//如果該位置還可以容納此員工，用sum記錄其在該處的喜好度
????????????????? {
??????????????????????? a[i]--;//該位置可容納員工數(shù)減1
??????????????????????? sum = p[man][i] + GetPlace(N, maxMen, man+1, p, a);
??????????????????????? a[i]++;
????????????????? }
????????????????? if (sum > max)
??????????????????????? max = sum;
??????????? }
????? }
????? return max; //返回第man到M個員工總的最大喜好度
}
?