軟件設計師案例分析當天每日一練試題地址：www.jazzmuze.com/exam/ExamDayAL.aspx?t1=4

往期軟件設計師每日一練試題匯總：www.jazzmuze.com/class/27/e4_1.html

軟件設計師案例分析每日一練試題（2022/9/16）在線測試：www.jazzmuze.com/exam/ExamDayAL.aspx?t1=4&day=2022/9/16

點擊查看：更多軟件設計師習題與指導

軟件設計師案例分析每日一練試題內容（2022/9/16）

閱讀下列說明和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)。
信管網試題答案與解析：www.jazzmuze.com/st/4177310833.html

信管網考友試題答案分享：

信管網cnitpm538497719640：
問題1： 1）c[i][j] 2）j ＞= w[i] 3）max（c[i-1][j-w[i]]+v[i], c[i-1][j]） 4）c[i][j] ＝ temp 問題2： 貪心策略、動態(tài)規(guī)劃法 問題3： 40

信管網suhx：
【問題1】： （1）：0， （2）：c[i][j] != 0， （3）：c[i][j]， （4）：c[i][j] ＝ temp， 【問題2】： 動態(tài)規(guī)劃設計策略，采用了自底向上的方式 【問題3】： 最大價值為40

信管網jac_luoziqiang：
（1）memoized_knapsack（int v（n）, int w（n）, int t）； （2） 動態(tài)規(guī)劃算法 自頂向下 3 40

信管網試題答案與解析：www.jazzmuze.com/st/4177310833.html