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