分享到微信
閱讀下列說明和C代碼，回答問題1至問題3。
【說明】
0-1背包問題定義為:給定i個物品的價值v[1…i]、小重量w[1...i]和背包容量T，每個物品裝到背包里或者不裝到背包里。求最優(yōu)的裝包方案，使得所得到的價值最大。
0-1背包問題具有最優(yōu)子結構性質。定義c[i][T]為最優(yōu)裝包方案所獲得的最大價值，則可得到如下所示的遞歸式。
【c代碼】
下面是算法的C語言實現。
(1)常量和變量說明
T: 背包容量
v[]:價值數組
w[]:重量數組
c[][]:c[i][j]表示前i個物品在背包容量為j的情況下最優(yōu)裝包方案所能獲得的最大價值
(2) C程序
【問題1】 (8分)
根據說明和C代碼，填充C代碼中的空(1) ~ (4)。
【問題2】 (4分)
根據說明和C代碼，算法采用了 (5) 設計策略。在求解過程中，采用了(6)
(自底向上或者自頂向下)的方式。
【問題3】 (3分)
若5項物品的價值數組和重量數組分別為v[]= {0,1,6,18,22,28}和w[]= {0,1,2,5,6,7}背包容量為T= 11,則獲得的最大價值為 (7)。
信管網參考答案：
【問題1】
(1)c[i][j]
(2)i>0&&j>=w[i]
(3)calculate_max_value(v,w,i-1,j-w[i])+v[i]
(4)c[i][j]=temp
【問題2】
(5)動態(tài)規(guī)劃
(6)自頂向下
【問題3】
(7)40
查看解析：www.xomuzic.com/st/4177310833.html
相關推薦：
掃碼關注公眾號
溫馨提示：因考試政策、內容不斷變化與調整，信管網網站提供的以上信息僅供參考，如有異議，請以權威部門公布的內容為準！
信管網致力于為廣大信管從業(yè)人員、愛好者、大學生提供專業(yè)、高質量的課程和服務，解決其考試證書、技能提升和就業(yè)的需求。
信管網軟考課程由信管網依托10年專業(yè)軟考教研傾力打造，官方教材參編作者和資深講師坐鎮(zhèn)，通過深研歷年考試出題規(guī)律與考試大綱，深挖核心知識與高頻考點，為學員考試保駕護航。面授、直播＆錄播，多種班型靈活學習，滿足不同學員考證需求，降低課程學習難度，使學習效果事半功倍。
相關內容
| 發(fā)表評論 查看完整評論 | |
考試新手指南
學習計劃攻略
精華備考資料
案例論文干貨
章節(jié)模擬試題
免費試聽課程
考試信息推送