軟件設計師案例分析當天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設計師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設計師案例分析每日一練試題（2022/5/25）在線測試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2022/5/25

點擊查看：更多軟件設計師習題與指導

軟件設計師案例分析每日一練試題內(nèi)容（2022/5/25）

試題四
閱讀下列說明，回答問題1至問題3，將解答填入對應欄內(nèi)。
【說明】
某餐廳供應各種標準的營養(yǎng)套餐。假設菜單上共有n項食物m1，m2，…，mn，每項食物mi的營養(yǎng)價值為vi，價格為pi其中i＝1，2，…，n，套餐中每項食物至多出現(xiàn)一次。客人常需要一個算法來求解總價格不超過M的營養(yǎng)價值最大的套餐。
【問題1】
下面是用動態(tài)規(guī)劃策略求解該問題的偽代碼，請?zhí)畛淦渲械目杖?1)、(2)和(3)處。
偽代碼中的主要變量說明如下。
n：總的食物項數(shù)；
v：營養(yǎng)價值數(shù)組，下標從1到n，對應第1到第n項食物的營養(yǎng)價值；
p：價格數(shù)組，下標從1到n，對應第1到第n項食物的價格；
M：總價格標準，即套餐的價格不超過M；
x：解向量(數(shù)組)，下標從1到n，其元素值為0或1，其中元素值為0表示對應的食物不出現(xiàn)在套餐中，元素值為1表示對應的食物出現(xiàn)在套餐中；
nv：n+1行M+1列的二維數(shù)組，其中行和列的下標均從0開始，nv[i][j]表示由前i項食物組合且價格不超過j的套餐的最大營養(yǎng)價值。問題最終要求的套餐的最大營養(yǎng)價值為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   (1)
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   (2)
16  x[i] ＝ 0
17  else
18  x[i] ＝ 1
19    (3)
20  return x and nv[n][M]
【問題2】
現(xiàn)有5項食物，每項食物的營養(yǎng)價值和價格如下表所示。

食物營養(yǎng)價值及價格表
若要求總價格不超過100的營養(yǎng)價值最大的套餐，則套餐應包含的食物有  (4)  (用食物項的編碼表示)，對應的最大營養(yǎng)價值為  (5)  。
【問題3】
問題1中偽代碼的時間復雜度為  (6)  (用O符號表示)。