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

来源:转载

【说明】

某公司供应各种标准的营养套餐。假设菜单上共有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)


分享给朋友:
您可能感兴趣的文章:
随机阅读: