試題四（共15 分）

閱讀下列說(shuō)明，回答問(wèn)題1至問(wèn)題3，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。

【說(shuō)明】

希賽公司供應(yīng)各種標(biāo)準(zhǔn)的營(yíng)養(yǎng)套餐。假設(shè)菜單上共有n項(xiàng)食物m₁，m₂，…，m_n，每項(xiàng)食物m_i的營(yíng)養(yǎng)價(jià)值為v_i，價(jià)格為p_i，其中i=1,2,…,n，套餐中每項(xiàng)食物至多出現(xiàn)一次?？腿顺Ｐ枰粋€(gè)算法來(lái)求解總價(jià)格不超過(guò)M的營(yíng)養(yǎng)價(jià)值最大的套餐。

【問(wèn)題1】（9 分）

下面是用動(dòng)態(tài)規(guī)劃策略求解該問(wèn)題的偽代碼，請(qǐng)?zhí)畛淦渲械目杖?1)、(2)和(3)處。

偽代碼中的主要變量說(shuō)明如下：

n： 總的食物項(xiàng)數(shù)；

v： 營(yíng)養(yǎng)價(jià)值數(shù)組，下標(biāo)從1到n，對(duì)應(yīng)第1到第n項(xiàng)食物的營(yíng)養(yǎng)價(jià)值；

p： 價(jià)格數(shù)組，下標(biāo)從1到n，對(duì)應(yīng)第1到第n項(xiàng)食物的價(jià)格；

M：總價(jià)格標(biāo)準(zhǔn)，即套餐的價(jià)格不超過(guò)M；

x： 解向量（數(shù)組），下標(biāo)從1到n，其元素值為0或1，其中元素值為0表示對(duì)應(yīng)的食物不出現(xiàn)在套餐中，元素值為1表示對(duì)應(yīng)的食物出現(xiàn)在套餐中；

nv：n+1行M+1列的二維數(shù)組，其中行和列的下標(biāo)均從0開(kāi)始，nv[i][j]表示由前i項(xiàng)食物組合且價(jià)格不超過(guò) j 的套餐的最大營(yíng)養(yǎng)價(jià)值。問(wèn)題最終要求的套餐的最大營(yíng)養(yǎng)價(jià)值為nv[n][M]。

[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]  [10]  [11]  [12]  [13]  [14]  [15]  [16]  [17]  [18]  [19]