軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

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

軟件設(shè)計(jì)師案例分析每日一練試題（2024/4/23）在線測試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2024/4/23

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2024/4/23）

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

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