閱讀下列說明和C代碼，回答問題1至問題3。

【說明】

0-1背包問題定義為:給定i個(gè)物品的價(jià)值v[1…i]、小重量w[1...i]和背包容量T，每個(gè)物品裝到背包里或者不裝到背包里。求最優(yōu)的裝包方案，使得所得到的價(jià)值最大。

0-1背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。定義c[i][T]為最優(yōu)裝包方案所獲得的最大價(jià)值，則可得到如下所示的遞歸式。

【c代碼】

下面是算法的C語言實(shí)現(xiàn)。

(1)常量和變量說明

T: 背包容量

v[]:價(jià)值數(shù)組

w[]:重量數(shù)組

c[][]:c[i][j]表示前i個(gè)物品在背包容量為j的情況下最優(yōu)裝包方案所能獲得的最大價(jià)值

(2) C程序

【問題1】 (8分)

根據(jù)說明和C代碼，填充C代碼中的空(1) ~ (4)。

【問題2】 (4分)

根據(jù)說明和C代碼，算法采用了 (5) 設(shè)計(jì)策略。在求解過程中，采用了(6)

(自底向上或者自頂向下)的方式。

【問題3】 (3分)

若5項(xiàng)物品的價(jià)值數(shù)組和重量數(shù)組分別為v[]= {0,1,6,18,22,28}和w[]= {0,1,2,5,6,7}背包容量為T= 11,則獲得的最大價(jià)值為 (7)。

信管網(wǎng)參考答案：

【問題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)動(dòng)態(tài)規(guī)劃

(6)自頂向下

【問題3】

(7)40

查看解析：www.tronclassroom.com/st/4177310833.html

相關(guān)推薦：

點(diǎn)擊查看/下載：軟件設(shè)計(jì)師歷年真題匯總

點(diǎn)擊查看：軟件設(shè)計(jì)師在線培訓(xùn)課程 丨 免費(fèi)試聽課程

免費(fèi)練習(xí)：軟件設(shè)計(jì)師考試題庫(模擬試題、章節(jié)練習(xí)、每日一練)