goal00001111

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