【說明】

　　某公司供應各種標準的營養套餐。假設菜單上共有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]。?

偽代碼如下：

　　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?nv[i-1][j]>=nv[i-1][j-p[i]]+v[i]

　　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?nv[i][j]=nv[i-1][j]
　　16????????????????x[i]?=?0
　　17??????????else
　　18????????????????x[i]?=?1
　　19????????????????j=j-p[i]
　　20????return?x?and?nv[n][M]?

?

【問題2】（4?分）

　　現有5項食物，每項食物的營養價值和價格如表4-1所示。

　　表?4-1??食物營養價值及價格表

編碼	營養價值	價格
m1	200	50
m2	180	30
m3	225	45
m4	200	25
m5	50	5

　　若要求總價格不超過100的營養價值最大的套餐，則套餐應包含的食物有m2,m3,m4（用食物項的編碼表示），對應的最大營養價值為?605。

【問題1】中偽代碼的時間復雜度為O(n*M)

轉載于:https://www.cnblogs.com/djcsch2001/archive/2011/07/01/2095914.html

總結

以上是生活随笔為你收集整理的软件设计师2008年12月下午试题4(C语言 动态规划)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。