软件设计师2008年12月下午试题4(C语言 动态规划)

简介: 【说明】   某公司供应各种标准的营养套餐。假设菜单上共有n项食物m1,m2,…,mn,每项食物mi的营养价值为vi,价格为pi,其中i=1,2,…,n,套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐。

【说明】

  某公司供应各种标准的营养套餐。假设菜单上共有n项食物m1,m2,…,mn,每项食物mi的营养价值为vi,价格为pi,其中i=1,2,…,n,套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐。

  【问题1】(9 分)

  下面是用动态规划策略求解该问题的伪代码,请填充其中的空缺(1)、(2)和(3)处。

  伪代码中的主要变量说明如下:

  n: 总的食物项数;

  v: 营养价值数组,下标从1到n,对应第1到第n项食物的营养价值;

  p: 价格数组,下标从1到n,对应第1到第n项食物的价格;

  M:总价格标准,即套餐的价格不超过M;

  x: 解向量(数组),下标从1到n,其元素值为0或1,其中元素值为0表示对应的食物不出现在套餐中,元素值为1表示对应的食物出现在套餐中;

  nv:n+1行M+1列的二维数组,其中行和列的下标均从0开始,nv[i][j]表示由前i项食物组合且价格不超过 j 的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。 

伪代码如下:

  MaxNutrientValue(n, v, p, M, x)
  1    for i = 0 to n
  2          nv[i][0] = 0
  3    for j = 1 to M
  4          nv[0][j] = 0
  5    for i = 1 to n
  6          for j = 1 to M
  7                  if j < p[i]    //若食物mi不能加入到套餐中
  8                        nv[i][j] = nv[i - 1][j]
  9                  else if nv[i-1][j]>=nv[i-1][j-p[i]]+v[i]

  10                      nv[i][j] =    nv[i - 1][j]
  11                else
  12                      nv[i][j] =    nv[i - 1][j – p[i]] + v[i]
  13    j = M
  14    for i = n downto 1
  15          if nv[i][j]=nv[i-1][j]
  16                x[i] = 0
  17          else
  18                x[i] = 1
  19                j=j-p[i]
  20    return x and nv[n][M] 

 

【问题2】(4 分)

  现有5项食物,每项食物的营养价值和价格如表4-1所示。

  表 4-1  食物营养价值及价格表

编码

营养价值

价格

m1

200

50

m2

180

30

m3

225

45

m4

200

25

m5

50

5

  若要求总价格不超过100的营养价值最大的套餐,则套餐应包含的食物有m2,m3,m4(用食物项的编码表示),对应的最大营养价值为 605。

【问题1】中伪代码的时间复杂度为O(n*M)

目录
打赏
0
相关文章
C语言进阶——指针进阶试题讲解(万字长文详解)
C语言进阶——指针进阶试题讲解(万字长文详解
55086 7
C语言进阶——指针进阶试题讲解(万字长文详解)
C语言进阶——指针进阶试题讲解(万字长文详解)
指针,一块存储其他内存块地址的空间,不仅能监管别人的地址信息,还拥有属于自己的地址。在取地址操作符(&)与解引用操作符(*)的“双重折磨”下,很多人对指针望而生畏,常常会掉进不规范使用指针而引发错误的大坑中。本文旨在通过众多例子来带大家理解指针(主要包含sizeof、strlen和多道指针笔试题),本文篇幅可能较长,请系好安全带,跟我走!
75 0
C语言进阶——指针进阶试题讲解(万字长文详解)
软件评测师2020年考试上午C语言试题解析
软件评测师2020年考试上午C语言试题解析
145 0
[软考考点解析]软件设计师--C语言存储空间
1. 题目 C程序中全局变量存储空间在____分配。 A 代码区 B 静态数据区 C 栈区 D 堆区
142 0
软件设计师2007年11月下午试题5(C语言 面向对象)
【说明】       在一个简化的绘图程序中,支持的图形种类有点(point)和圆(circle),在设计过程中采用面向对象思想,认为所有的点和圆都是一种图形(shape),并定义了类型shape_t、point_t和circle_t分别表示基本图形、点和圆,并且点和圆具有基本图形的所有特征。
805 0
软件设计师2005年11月试题4(C语言 散列文件存储)
散列文件的存储单位称为桶(BUCKET) 。假如一个桶能存放m个记录,当桶中已有m个同义词(散列函数值相同)的记录时,存放第m+1 个同义词会发生"溢出"。此时需要将第m+1 个同义词存放到另一个称为"溢出桶"的桶中。
719 0
软件设计师2006年5月试题5(C语言 多叉平衡查找树)
B树是一种多叉平衡查找树。一棵m阶的B树,或为空树,或为满足下列特性的m叉树:  ①树中每个结点至多有m棵子树;  ②若根结点不是叶子结点,则它至少有两棵子树;  ③除根之外的所有非叶子结点至少有「m/2]棵子树;  ④所有的非叶子结点中包含卞列数据信息   (n,A0,K1,A1,K2,...
678 0
软件设计师2006年11月下午试题5(C语言 树及其孩子-兄弟表示)
[说明]  一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图 5-1(a) 所示的树的孩子-兄弟表示如图 5-1(b)所示。
955 0
【C语言】字符串操作函数详解
这些字符串操作函数在C语言中提供了强大的功能,帮助开发者有效地处理字符串数据。通过对每个函数的详细讲解、示例代码和表格说明,可以更好地理解如何使用这些函数进行各种字符串操作。如果在实际编程中遇到特定的字符串处理需求,可以参考这些函数和示例,灵活运用。
62 10
【C语言】文件操作函数详解
C语言提供了一组标准库函数来处理文件操作,这些函数定义在 `<stdio.h>` 头文件中。文件操作包括文件的打开、读写、关闭以及文件属性的查询等。以下是常用文件操作函数的详细讲解,包括函数原型、参数说明、返回值说明、示例代码和表格汇总。
50 9
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等