【说明】

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