試題四（共15 分）

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

【說明】

希賽公司供應(yīng)各種標(biāo)準(zhǔn)的營養(yǎng)套餐。假設(shè)菜單上共有n項食物m₁，m₂，…，m_n，每項食物m_i的營養(yǎng)價值為v_i，價格為p_i，其中i=1,2,…,n，套餐中每項食物至多出現(xiàn)一次。客人常需要一個算法來求解總價格不超過M的營養(yǎng)價值最大的套餐。

【問題1】（9 分）

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

偽代碼中的主要變量說明如下：

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

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

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

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項食物組合且價格不超過 j 的套餐的最大營養(yǎng)價值。問題最終要求的套餐的最大營養(yǎng)價值為nv[n][M]。

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