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

Posted on 2006-05-30 13:53 梦想飞扬 阅读(1785) 评论(8)  编辑 收藏 引用

Feedback

# re: 我解百度之星题目之" 饭团的烦恼 "   回复  更多评论   

2006-06-15 16:50 by efafwedsa
汗~~~~~~~~运行时内存出错了

# re: 我解百度之星题目之" 饭团的烦恼 "   回复  更多评论   

2006-06-15 21:07 by goal00001111
不可能啊!
你没有创建文件in3.txt到当前目录吧

# re: 我解百度之星题目之" 饭团的烦恼 "   回复  更多评论   

2007-05-21 00:29 by oyjpart
lz是不是写的麻烦了点
#include <stdio.h>
#include <string.h>
#include <math.h>

const int N = 17;

int main() {
int i, a, b, c, d, x, best = -10000, rec = -1, nc, need, np, hun[N], la[N], su[N], dan[N], p[N], sum[4];
char name[N][100];
scanf("%d %d %d", &nc, &need, &np);
for(i = 0; i < nc; i++) {
scanf("%s %d %d %d", &name[i], &p[i], &hun[i], &la[i]);
su[i] = 1-hun[i]; dan[i] = 1-la[i];
}
scanf("%d %d %d %d", &a, &b, &c, &d);
for(x = 0; x < (1<<nc); ++x) {
memset(sum, 0, sizeof(sum));
int price = 0, cnt = 0;
for(i = 0; i < nc; ++i)
if( (x & (1<<i)) != 0) {
cnt++; price += p[i];
}

if(cnt != need || abs(price - np * 12) >= abs(best - np * 12)) continue;
for(i = 0; i < nc; ++i)
if( (x & (1<<i)) != 0) {
sum[0] += hun[i]; sum[1] += su[i];
sum[2] += la[i]; sum[3] += dan[i];
}

if(sum[0] == a && sum[1] == b && sum[2] == c && sum[3] == d) {
best = price; rec = x;
}
}
for(i = 0; i < nc; i++)
if( (rec & (1<<i)) != 0)
puts(name[i]);
printf("%.2lf\n", 0.8* best / np);
return 0;
}

# re: 我解百度之星题目之" 饭团的烦恼 "   回复  更多评论   

2007-05-21 00:35 by oyjpart
一点修改 if(cnt != need || abs(price - np * 12) >= abs(best - np * 12)) continue; 中的 12->15

# re: 我解百度之星题目之" 饭团的烦恼 "   回复  更多评论   

2008-12-13 14:40 by 远风
貌似效率问题.....

# re: 我解百度之星题目之" 饭团的烦恼 "   回复  更多评论   

2009-05-07 22:42 by xxoo
怀疑那个给出的例子是怎么计算到12元的人均消费....

# re: 我解百度之星题目之" 饭团的烦恼 "   回复  更多评论   

2009-11-19 21:56 by crazy
大哥 拿你的去搞半天还是有错误 QQ442065168 希望能讨论

# re: 我解百度之星题目之" 饭团的烦恼 " [未登录]  回复  更多评论   

2010-02-12 10:47 by leo

#include <stdio.h>
#include <string.h>
#include <math.h>

const int N = 17;

int main() {
int i, a, b, c, d, x, best = -10000, rec = -1, nc, need, np, hun[N], la[N], su[N], dan[N], p[N], sum[4];
char name[N][100];
scanf("%d %d %d", &nc, &need, &np);
for(i = 0; i < nc; i++) {
scanf("%s %d %d %d", &name[i], &p[i], &hun[i], &la[i]);
su[i] = 1-hun[i]; dan[i] = 1-la[i];
}
scanf("%d %d %d %d", &a, &b, &c, &d);
for(x = 0; x < (1<<nc); ++x) {
memset(sum, 0, sizeof(sum));
int price = 0, cnt = 0;
for(i = 0; i < nc; ++i)
if( (x & (1<<i)) != 0) {
cnt++; price += p[i];
}



if(cnt != need || abs(price - np * 15) >= abs(best - np * 15)) continue;
for(i = 0; i < nc; ++i)
if( (x & (1<<i)) != 0)
{
sum[0] += hun[i]; sum[1] += su[i];
sum[2] += la[i]; sum[3] += dan[i];
}

if(sum[0] == a && sum[1] == b && sum[2] == c && sum[3] == d) {
best = price; rec = x;
}
}
for(i = 0; i < nc; i++)
if( (rec & (1<<i)) != 0)
puts(name[i]);
printf("%.2lf\n", 0.8* best / np);
return 0;
}



只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理