2019下半年軟件設(shè)計(jì)師下午真題(四)

軟件設(shè)計(jì)師 責(zé)任編輯:胡媛 2019-11-20

添加老師微信

備考咨詢

加我微信

摘要:希賽網(wǎng)軟考頻道小編為大家整理了2019下半年軟件設(shè)計(jì)師下午真題,以下為軟件設(shè)計(jì)師下午考試真題第四部分:

4、閱讀下列說(shuō)明和C代碼,回答問(wèn)題1至問(wèn)題3。

【說(shuō)明】

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

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

prog6.jpg

【c代碼】

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

(1)常量和變量說(shuō)明

T: 背包容量

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

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

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

(2) C程序

prog7.jpg

問(wèn)題內(nèi)容:

【問(wèn)題1】 (8分)

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

【問(wèn)題2】 (4分)

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

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

【問(wèn)題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)。

更多資料
更多課程
更多真題
溫馨提示:因考試政策、內(nèi)容不斷變化與調(diào)整,本網(wǎng)站提供的以上信息僅供參考,如有異議,請(qǐng)考生以權(quán)威部門公布的內(nèi)容為準(zhǔn)!

軟考備考資料免費(fèi)領(lǐng)取

去領(lǐng)取

!
咨詢?cè)诰€老師!