/*
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(); //关闭文件
}