軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計(jì)師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設(shè)計(jì)師案例分析每日一練試題（2024/5/20）在線測(cè)試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2024/5/20

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2024/5/20）

閱讀下列說明和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)試題答案與解析：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2024/5/20

信管網(wǎng)考友試題答案分享：

信管網(wǎng)cnitpm610258705267：
1：return c[i][j] 2:j＞=w[i] 3:c[i-1][j] 4:c[i][j]=temp 5：動(dòng)態(tài)規(guī)劃 6 自頂向下 7：35

信管網(wǎng)cnitpm610258705267：
1：return c[i][j] 2:j＞=w[i] 3:c[i-1][j] 4:c[i][j]=temp 5：動(dòng)態(tài)規(guī)劃 6 自頂向下 7：35

信管網(wǎng)cnitpm633797129230：
問題1： c[i][j],i＞0&&j＞=w[i],calcute_max_value（v,w,i-1,j-w[i]）+v[i],c[i][j]=temp 問題2： 動(dòng)態(tài)規(guī)劃，自頂向下 問題3： 40

信管網(wǎng)cnitpm630501712623：
【問題1】 1. c[i][j] 2. i ＞ 0 && j ＞= w[i] 3. c[i-1][j] 4.c[i][j]=temp 【問題2】 遞歸，自底向上 【問題3】

信管網(wǎng)cnitpm563675966604：
1） c[i][j]；  ＜br＞2） j＞=w[i]；  ＜br＞3） calculate_max_value（v,w,i-1,j-w[i]）+v[i]；  ＜br＞4） c[i][j]=temp ＜br＞5） 遞歸 ＜br＞6）自底向上

信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2024/5/20