/*
? 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個員工總的最大喜好度
}
?