軟件設(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/9/30）在線測試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2024/9/30

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

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

閱讀下列說明，回答問題1至問題2，將解答填入答題紙的對應(yīng)欄內(nèi)。
【說明】
0-1背包問題可以描述為：有n個物品，對i=1，2，…，n，第i個物品價值為vi ，重量為wi（vi，和wi為非負(fù)數(shù)），背包容量為W（W為非負(fù)數(shù)），選擇其中一些物品裝入背包，使裝入背包物品的總價值最大，即，且總重量不超過背包容量，即，其中，xi∈{0，1}，xi=0表示第i個物品不放入背包，xi=1表示第i個物品  放入背包。
?【問題1】（8分）
用回溯法求解此0-1背包問題，請?zhí)畛湎旅鎮(zhèn)未a中（1）~（4）處空缺。
回溯法是一種系統(tǒng)的搜索方法。在確定解空間后，回溯法從根結(jié)點(diǎn)開始，按照深度優(yōu)先策略遍歷解空間樹，搜索滿足約束條件的解。對每一個當(dāng)前結(jié)點(diǎn)，若擴(kuò)展該結(jié)點(diǎn)己經(jīng)不滿足約束條件，則不再繼續(xù)擴(kuò)展。為了進(jìn)一步提高算法的搜索效率，往往需要設(shè)計(jì)一個限界函數(shù)，判斷并剪枝那些即使擴(kuò)展了也不能得到最優(yōu)解的結(jié)點(diǎn)。現(xiàn)在假設(shè)已經(jīng)設(shè)計(jì)了BOUND（v，w，k，W）函數(shù)，其中v， w， k和W分別表示當(dāng)前已經(jīng)獲得的價值、當(dāng)前背包的重量、己經(jīng)確定是否選擇的物品數(shù)和背包的總?cè)萘?。對?yīng)于搜索樹中的某個結(jié)點(diǎn)，該函數(shù)值表示確定了部分物品是否選擇之后，對剩下的物品在滿足約束條件的前提下進(jìn)行選擇可能獲得的最大價值，若該價值小于等于當(dāng)前已經(jīng)得到的最優(yōu)解，則該結(jié)點(diǎn)無需再擴(kuò)展。
下面給出0-1背包問題的回溯算法偽代碼。
函數(shù)參數(shù)說明如下：
W：背包容量；n：物品個數(shù)；w：重量數(shù)組；v：價值數(shù)組；fw：獲得最大價值時背包的重量；fp：背包獲得的最大價值；X：問題的最優(yōu)解。
變量說明如下：
cw：當(dāng)前的背包重量；cp：當(dāng)前獲得的價值；k：當(dāng)前考慮的物品編號；Y：當(dāng)前已獲得的部分解。

?【問題2】（7分）
考慮表4-1的實(shí)例，假設(shè)有3個物品，背包容量為22。圖4-1中是根據(jù)上述算法構(gòu)造的搜索樹，其中結(jié)點(diǎn)的編號表示了搜索樹生成的順序，邊上的數(shù)字1/0分別表示選擇／不選擇對應(yīng)物品。除了根結(jié)點(diǎn)之外，每個左孩子結(jié)點(diǎn)旁邊的上下兩個數(shù)字分別表示當(dāng)前背包的重量和已獲得的價值，右孩子結(jié)點(diǎn)旁邊的數(shù)字表示擴(kuò)展了該結(jié)點(diǎn)后最多可能獲得的價值。為獲得最優(yōu)解，應(yīng)該選擇物品 （5） ，獲得的價值為 （6） 。

對于表4-1的實(shí)例，若采用窮舉法搜索整個解空間，則搜索樹的結(jié)點(diǎn)數(shù)為 （7） ，而用了上述回溯法，搜索樹的結(jié)點(diǎn)數(shù)為 （8） 。
信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2024/9/30

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

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