2008年下半年軟件設計師下午試卷[11]
摘要：試題四（共15分）閱讀下列說明，回答問題1至問題3，將解答填入答題紙的對應欄內。【說明】希賽公司供應各種標準的營養套餐。假設菜單上共有n項食物m1，m2，…，mn，每項食物mi的營養價值為vi，價格為pi，其中i=1,2,…,n，套餐中每項食物至多出現一次。客人常需要一個算法來求解總價格不超過M的營養價值最大的套餐。【問題1】（9分）下
試題四（共15 分）
閱讀下列說明，回答問題1至問題3，將解答填入答題紙的對應欄內。
【說明】
希賽公司供應各種標準的營養套餐。假設菜單上共有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]。
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19]
延伸閱讀
軟考備考資料免費領取
去領取
- 0
- 4
- 6
專注在線職業教育25年
APP 
微信群 
掃描二維碼
掃描二維碼
