?/*
? Name:
? Copyright:
? Author:
? Date: 28-05-07 15:26
? Description: 2.飯團的煩惱
“午餐飯團”是百度內部參與人數最多的民間組織。
同一個部門的、同一所大學的、同一年出生的、使用同一種型號電腦的員工們總是以各種理由組織各種長期的、臨時的飯團。
參加飯團，不僅可以以優惠的價格嘗到更加豐富的菜式，還可以在吃飯的時候和同事們增進感情。
但是，隨著百度的員工越來越多，各個飯團的管理變得繁雜起來。特別是為了照顧員工們越來越挑剔的胃，飯團的點菜負責人的壓力也越來越大。現在，這個任務就交給“百度之星”了，因為，你將要為所有的百度飯團設計一個自動點菜的算法。
飯團點菜的需求如下：
1．經濟是我們要考慮的一個因素，既要充分利用百度員工的午餐補助，又不能鋪張浪費。因此，我們希望最后的人均費用越接近12元越好。
2．菜式豐富是我們要考慮的另一個因素。為簡單起見，我們將各種菜肴的屬性歸結為葷菜，素菜，辛辣，清淡，并且每個菜只能點一次。
3．請謹記，百度飯團在各大餐館享受8折優惠。
輸入要求：
1．輸入數據第一行包含三個整數N，M，K(0<N<=16，0<M<=N，0<K<=12)，分別表示菜單上菜的數目，飯團需要點的菜的數目，就餐的人數；
2．緊接著N行，每行的格式如下：
菜名（長度不超過20個字符） 價格（原價，整數） 是否葷菜（1表示是，0表示否） 是否辛辣（1表示是，0表示否）；
3．第N+2行是 a b c d 四個整數，分別表示需要點的葷菜，素菜，辛辣，清淡菜的數目。例：
3 2 2
水煮魚 30 1 1
口水雞 18 1 1
清燉豆腐 12 0 0
1 1 1 1
?
輸出要求：
對于每組測試數據，輸出數據包含M+1行，前M行每行包含一個菜名（按菜名在原菜單的順序排序）。第M+1行是人均消費，結果保留兩位小數。例：
口水雞
清燉豆腐
12.00
評分規則：
1．程序將運行在一臺Linux機器上（內存使用不作嚴格限制），在每一測試用例上運行不能超過10秒，否則該用例不得分；
2．要求程序能按照輸入樣例的格式讀取數據文件，按照輸出樣例的格式將運行結果輸出到標準輸出上。如果不能正確讀入數據和輸出數據，該題將不得分；
3．該題目共有5個測試用例，每個測試用例為一個輸入文件。各測試用例占該題目分數的比例分別為20%，20%，20%，20%，20%；
4．該題目10分。
*/
/*
算法介紹：
1。讀入數據。
2。以菜的個數為主序，采用回溯的方法依次處理每個菜的可能性，返回最好的點菜方法:
????? 即將問題轉化為：從N個不同的數中選出滿足要求的M個數。
????? 解決辦法為先從N個不同的數中選出M個數，再判斷這M個數是否滿足要求，滿足要求則存儲到數組bestdish[]，并根據當前實際最佳金額與理論最佳金額的差值，實時更換數組bestdish[]的值，最后得到的數組bestdish[]就是最佳數組bestdish[]。
3。根據數組bestdish[]，輸出結果。
*/
#include <iostream>
#include<fstream>
#include <time.h>
using namespace std;
const int MAX = 21;
double Min = 1000000;//存儲當前實際最佳金額與理論最佳金額的差值
double pay; //存儲當前實際最佳金額
double bestPay; //存儲所需的理論最佳金額，恰好每人12元
int N, M, K;
int hunCai;
int suCai;
int xinLa;
int qingDan;
class Dish{
public:
????? char name[MAX];
????? double price;
????? bool isMeat;
????? bool isAcridity;
????? void PutData(const char *na, double p, bool m, bool acr) //輸入數據
????? {
??????????? strcpy(name, na);
??????????? price = p;
??????????? isMeat = m;
??????????? isAcridity = acr;
????? }
????? void PrintData()
????? {
??????????? cout << name << ' ' << price << ' ' << isMeat << ' ' << isAcridity << endl;
????? }
};
void ReadData(const char *filename, Dish **obj);
double Abs(double a);
bool IsPass(const int pass[], const Dish *obj, double & sum);
void GetDishes(int num, int pos, const Dish *obj, int pass[], int bestDish[]);
int main()
{
?time_t startTime;
?time_t endTime;
?time(&startTime);
????? Dish *obj;
?ReadData("in3.txt", &obj);//讀入數據
?//cout << N << ' ' << M << ' ' << K << endl;
//?for (int i=0; i<N; i++)
//??????????? obj[i].PrintData();
//????? cout << hunCai << ' ' << suCai << ' ' << xinLa << ' ' << qingDan << endl;
????? bestPay = K * 12; //存儲所需的理論最佳金額，恰好每人12元
????? int *pass = new int[N+1]; //存儲已經被點了的菜
????? int *bestDish = new int[N+1]; //存儲最佳被點了的菜
????? GetDishes(1, 0, obj, pass, bestDish); //以菜的個數用回溯的方法求最佳點菜方案
?????
????? for (int i=1; i<=M; i++)
????? {
??????????? cout << obj[bestDish[i]].name << endl;
????? }
????? printf("%.2f\n", pay / K);
?????
????? delete []pass;
????? delete []bestDish;
?????
?time(&endTime);
//?cout << difftime(endTime, startTime) << endl;
?getchar();
?return 0;
}
void GetDishes(int num, int pos, const Dish *obj, int pass[], int bestDish[])
{
????? if (num == M)//處理最后一個菜
????? {
??????????? for (int i=pos; i<N; i++)
??????????? {
????????????????? pass[num] = i;
????????????????? double sum = 0;
????????????????? if (IsPass(pass, obj, sum) && Abs(sum-bestPay)<Min) //若該道菜滿足口味要求，并最接近理論最佳金額
????????????????? {
??????????????????????? pay = sum;? //存儲當前實際最佳金額
??????????????????????? Min = Abs(sum-bestPay);//存儲當前最小差別
??????????????????????? for (int i=1; i<=M; i++)
????????????????????????????? bestDish[i] = pass[i];
????????????????? }
??????????? }
????? }
????? else //如果處理的不是最后一個菜，應采用回溯方法以取得最優解
????? {
??????????? for (int i=pos; i<N-M+num; i++)
??????????? {
???????????????? pass[num] = i;
???????????????? GetDishes(num+1, i+1, obj, pass, bestDish);
??????????? }
????? }
}
bool IsPass(const int pass[], const Dish *obj, double & sum)
{
????? int h = 0; //存儲實際已經點了的葷菜
????? int s = 0; //存儲實際已經點了的素菜
????? int x = 0; //存儲實際已經點了的辛辣菜
????? int q = 0; //存儲實際已經點了的清淡菜
????? for (int j=1; j<=M; j++)
????? {
??????????? sum += obj[pass[j]].price * 0.8;
??????????? if (obj[pass[j]].isMeat && h < hunCai)//分析該道菜的各種屬性
????????????????? h++;
??????????? else if (!obj[pass[j]].isMeat && s < suCai)
????????????????? s++;
??????????? else
????????????????? return false;
??????????? if (obj[pass[j]].isAcridity && x < xinLa)
????????????????? x++;
??????????? else if (!obj[pass[j]].isAcridity && q < qingDan)
????????????????? q++;
??????????? else
????????????????? return false;
????? }
????? return true;
}
double Abs(double a)
{
????? return (a > 0) ? a : -a;
}
void ReadData(const char *filename, Dish **obj)
{
????? fstream in(filename);
????? if (!in)
??????????? return ;?? //結束程序執行
????? in >> N;
????? in >> M;
????? in >> K;
????? *obj = new Dish[N];
????? int n = 0;
????? while (!in.eof() && n < N)
????? {
??????????? char name[MAX];
??????????? double price;
??????????? bool isMeat;
??????????? bool isAcridity;
??????????? in >> name;
??????????? in >> price;
??????????? in >> isMeat;
??????????? in >> isAcridity;
??????????? (*obj)[n++].PutData(name, price, isMeat, isAcridity);
????? }
????? in >> hunCai;
????? in >> suCai;
????? in >> xinLa;
????? in >> qingDan;
????? in.close(); //關閉文件
}