[渴婴问题] 有一个非常渴的、聪明的小婴儿,她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水,即婴儿可得到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;
}
分享到:
相关推荐
用贪心算法解单源最短路径问题 明确单源最短路径问题的概念;利用贪心算法解决单源最短路径问题;并通过本例熟悉贪心算法在程序设计中的应用方法。
贪心算法之最优合并问题
贪心算法 贪心算法 贪心算法 贪心算法 贪心算法 贪心算法
贪心算法的应用 贪心算法的应用 贪心算法的应用 贪心算法的应用
贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法
基于最小堆和贪心算法求解多机调度问题基于最小堆和贪心算法求解多机调度问题基于最小堆和贪心算法求解多机调度问题基于最小堆和贪心算法求解多机调度问题基于最小堆和贪心算法求解多机调度问题基于最小堆和贪心算法...
贪心算法 背包问题 c语言 绝对无误 运行成功
实验2装箱问题-贪心算法
贪心算法贪心算法贪心算法贪心算 背包问题背包问题背包问题
贪心算法之汽车加油问题
贪心算法 贪心算法的理解 贪心算法的算法 贪心算法的讲解
使用贪心算法求解tsp问题,使用vc实现,资源中包含有程序的文档,包含tsp问题说明、贪心算法分析和程序源码。
活动安排问题是利用贪心算法有效求解的很好例子。该问题要求高校的安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法,使尽可能多的活动可以兼容的使用某一公共资源
多机调度问题的贪心算法实现。示例代码,可直接在VC上运行。
贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言...问题贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现...
贪心算法之装箱问题,使用c语言来实现的,贪心算法之装箱问题,使用c语言来实现的,
贪心算法 找零钱 c语言 简洁 绝对无误
贪心算大实现活动安排问题,算法实现使用图形界面动态显示,程序中用到的排序算法为快速排序
贪心算法在背包问题中的应用贪心算法在背包问题中的应用 C 语言代码
贪心算法之会场安排问题,直接可运行,python文件