`
Riddick
  • 浏览: 646165 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

贪心算法应用之渴婴问题

阅读更多

 [渴婴问题] 有一个非常渴的、聪明的小婴儿,她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水,即婴儿可得到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;
}

  

 

 

分享到:
评论

相关推荐

    用贪心算法解单源最短路径问题

    贪心算法是解决单源最短路径问题的一种常用方法,本文将详细介绍贪心算法在单源最短路径问题中的应用。 一、贪心算法原理 贪心算法是一种近似算法,它的基本思想是逐步构造最优解。在每个阶段,都作出一个看上去...

    贪心算法之最优合并问题.zip

    本资料包"贪心算法之最优合并问题.zip"显然是针对贪心算法在合并问题中的应用进行深入探讨,特别提到了Python编程语言的实现。 首先,我们要理解贪心算法的基本思想。在解决一个问题时,贪心算法不考虑全局最优解,...

    tsp问题贪心算法求解

    **贪心算法与旅行商问题(TSP)** 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法策略。它并不考虑整个问题的全局最优解,而是每一步都...

    贪心算法之会场安排问题.zip

    会场安排问题就是一种典型的贪心算法应用实例。 在会场安排问题中,我们通常面临这样的场景:有多个会议需要在一个有限的会场里进行,每个会议都有其开始和结束时间,并且要求一个会场在同一时间内只能安排一个会议...

    贪心算法之磁盘文件最优储存问题.zip

    本压缩包文件“贪心算法之磁盘文件最优储存问题.zip”提供了相关的Python代码示例,可以在PyCharm或其他Python环境中运行。 首先,我们需要理解磁盘文件的存储问题。磁盘通常有多个扇区,每个扇区可以存储一定大小...

    贪心算法 贪心算法 贪心算法 贪心算法

    贪心算法 贪心算法 贪心算法 贪心算法 贪心算法 贪心算法

    贪心算法,最小生成树

    贪心算法和最小生成树 贪心算法是指在解决问题时,总是做出在当前看来最好的选择,以期望能够得到最终的最优解。...通过理解贪心算法的基本要素和理论基础,我们可以更好地应用贪心算法来解决实际问题。

    用贪心算法求解最优服务次序问题

    "贪心算法在最优服务次序问题中的应用" 贪心算法是解决问题的一类重要方法,以其简单、直观和高效而受到人们的重视。特别是对于具有最优子结构和贪心选择性质的一类实际问题,它可以通过一系列局部最优选择来获得...

    用贪心算法实现背包问题

    数据库管理和Web开发同样需要高效的问题解决策略,贪心算法在这些领域都有潜在的应用价值。 总之,贪心算法在解决背包问题时提供了一种简洁且直观的方法。在Java编程环境中,我们可以利用数据结构和算法的优势,...

    贪心算法 部分背包问题

    这个“实验二a”程序可能是为了让学生理解和实践贪心算法在部分背包问题中的应用,从而提高他们对算法设计和问题求解的能力。通过分析和修改这个程序,学生可以深入理解贪心算法的原理,以及它与背包问题的适应性。...

    贪心算法 背包问题 c语言

    ### 贪心算法在背包问题中的应用及C语言实现 #### 一、贪心算法简介 贪心算法是一种在每个步骤中都选择局部最优解的策略,希望通过一系列的局部最优选择来达到全局最优解的目的。它适用于某些特定的问题类型,在...

    贪心算法求解tsp(旅行商问题)

    9. **文档和源码**:提供的资源中可能包含了关于TSP问题的文档,详细解释了问题背景和贪心算法的分析,以及源代码,展示了如何在实际编程中应用这些概念。 10. **测试和调试**:为了确保算法的有效性,需要编写测试...

    贪心算法活动安排问题,

    ### 贪心算法在活动安排问题中的应用 #### 一、引言 在计算机科学领域,贪心算法是一种在每个步骤中都选择局部最优解的策略,希望通过这种方式找到全局最优解。活动安排问题(Activity Selection Problem)是贪心...

    贪心算法、分治算法和动态规划的区别 贪心算法和动态规划.pdf

    虽然能够应用贪心算法一定能够应用动态规划法,但是一般来说,贪心算法的效率高于动态规划法,因而还是应用贪心算法。 动态规划法和分治法的区别 动态规划法和分治法的共同点是,二者都要求原问题具有最优子结构...

    贪心算法贪心算法背包问题

    根据给定的文件信息,我们将深入探讨“贪心算法”在解决背包问题中的应用与实现。贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择策略,以便产生全局最优解的算法。然而,值得注意的是...

    贪心算法 背包问题 C语言

    在解决背包问题时,贪心算法的应用尤为常见,尤其是对于部分背包问题。 0-1背包问题是最基础的形式,其中每个物品要么完全放入背包,要么完全不放。但在部分背包问题中,我们可以选择物品的一部分进行装入,这样...

    贪心算法之汽车加油问题.zip

    在这个“汽车加油问题”中,我们将探讨如何应用贪心算法解决实际问题。 假设我们有一辆汽车,从起点出发,需要经过一系列距离到达终点,并且汽车的油箱容量有限。汽车在途中的每个加油站都可以加油,但不允许超过...

    多机调度问题贪心算法基于最小堆和贪心算法求解多机调度问题.zip

    基于最小堆和贪心算法求解多机调度问题基于最小堆和贪心算法求解多机调度问题基于最小堆和贪心算法求解多机调度问题基于最小堆和贪心算法求解多机调度问题基于最小堆和贪心算法求解多机调度问题基于最小堆和贪心算法...

    贪心算法 贪心 算法 贪心的算法

    举个例子,经典的贪心算法问题包括: - **霍夫曼编码**:在数据压缩中,贪心算法用于构建霍夫曼树,通过对字符出现频率的排序,每次合并频率最低的两个节点,直到只剩下一个节点,这个过程保证了频繁出现的字符有较...

Global site tag (gtag.js) - Google Analytics