贪心算法应用之渴婴问题

 [渴婴问题] 有一个非常渴的、聪明的小婴儿，她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得到n种不同的饮料。根据以前关于这n种饮料的不同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下方法为每一种饮料赋予一个满意度值：饮用1盎司第i 种饮料，对它作出相对评价，将一个数值si 作为满意度赋予第i 种饮料。

 

通常，这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满足她解渴的需要，但是不幸的是：具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设ai是第i 种饮料的总量（以盎司为单位），而此婴儿需要t盎司的饮料来解渴，那么，需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求呢？

#include <iostream>
using namespace std;

typedef struct tagBeverage
{
   char beveName[20];         //饮料名称
   int beveMeasure;              //饮料的数量
   int beveSactisfaction;        //婴儿对该饮料的满意度
}BEVERAGE, *PBEVERAGE;

//婴儿所需饮料总数
int baby_require = 100;

//初始化饮料数组
BEVERAGE beveArray[3] = {{"water", 10, 60}, {"coco", 40, 40}, {"pasi", 80, 80}};

//寻找满意度最高的饮料ID
int findHighestSactisfy(BEVERAGE beveArray[], int n, int highestBeve=0, int highestBeveSatisfy=0)
{
   for(int i=0; i<n; i++)
   {
      if((beveArray[i].beveSactisfaction > highestBeveSatisfy) && (beveArray[i].beveMeasure > 0))        
      {
         highestBeve = i;
         highestBeveSatisfy = beveArray[i].beveSactisfaction;                                  
      }
   }   
   return highestBeve; 
}

//算法函数
void satisfyThirsty(BEVERAGE beveArray[], int n)
{
   int i, highestBeve=0, highestSatisfy=0;
   do
   {
      i = findHighestSactisfy(beveArray, 3);
      if((baby_require -= beveArray[i].beveMeasure) > 0)
      {
         cout<<"Baby enjoyed "<<beveArray[i].beveName<<" "
                     <<beveArray[i].beveMeasure<<"Ansi"<<endl;
         cout<<"Beverage sactisfaction is "<<beveArray[i].beveSactisfaction<<endl;
         beveArray[i].beveMeasure = 0;
      }
      else 
      {
         beveArray[i].beveMeasure -= baby_require;
         baby_require = 0;
         cout<<"Baby enjoyed "<<beveArray[i].beveName<<" "
                     <<baby_require<<"Ansi"<<endl;
         cout<<"Beverage sactisfaction is "<<beveArray[i].beveSactisfaction<<endl;     
      }
      cout<<"Beverage "<<beveArray[i].beveName<<" left "<<beveArray[i].beveMeasure<<"Ansi"<<endl;
   }while(baby_require);   
}

int main()
{
   satisfyThirsty(beveArray, 3);
   system("pause");
   return 0;
}