試題四
閱讀下列說明，回答問題1至問題2。
[說明]
0-1背包問題可以描述為：有n個物品，對i=1，2，…，n，第i個物品價值為vi重量為wi(vi和wi非負數(shù))，背包容量為W(W為非負數(shù))，選擇其中一些物品裝入背包，使裝入背包物品的總價值最大，

個物品不放入背包，xi=1表示第i個物品放入背包。
【問題1】用回溯法求解此0-1背包問題，請?zhí)畛湎旅鎮(zhèn)未a中(1)～(4)處空缺。
回溯法是一種系統(tǒng)的搜索方法。在確定解空間后，回溯法從根結(jié)點開始，按照深度優(yōu)先策略遍歷解空間樹，搜索滿足約束條件的解。對每一個當前結(jié)點，若擴展該結(jié)點已經(jīng)不滿足約束條件，則不再繼續(xù)擴展。為了進一步提高算法的搜索效率，往往需要設(shè)計一個限界函數(shù)，判斷并剪枝那些即使擴展了也不能得到最優(yōu)解的結(jié)點。現(xiàn)在假設(shè)已經(jīng)設(shè)計了BOUND(v，w，k，W函數(shù)，其中v、w、k和W分別表示當前已經(jīng)獲得的價值、當前背包的重量、已經(jīng)確定是否選擇的物品數(shù)和背包的總?cè)萘俊?yīng)于搜索樹中的某個結(jié)點，該函數(shù)值表示確定了部分物品是否選擇之后，對剩下的物品在滿足約束條件的前提下進行選擇可能獲得的最大價值，若該價值小于等于當前已經(jīng)得到的最優(yōu)解，則該結(jié)點無需再擴展。
下面給出0-1背包問題的回溯算法偽代碼。
函數(shù)參數(shù)說明如下：
W：背包容量；n：物品個數(shù)；w：重量數(shù)組；v：價值數(shù)組；fw：獲得最大價值時背包的重量；fp：背包獲得的最大價值；X：問題的最優(yōu)解。
變量說明如下：
cw：當前的背包重量；cp：當前獲得的價值；k：當前考慮的物品編號；Y：當前已獲得的部分解。
BKNAP(W，n，w，v，fw，fp，x)
1 cw←cp←0
2   (1)
3 fp←-1
4 while true
5    while  k≤n and cw+w[k]  ≤W do
6            (2)
7          cp←cp十v[k]
8          Y[k]←l
9          k←k+1
10    if k＞n then
11         if fp＜cp then
12               fp←cp
13               fw←cw
14               k←n
15               X←Y
16    else Y(k)←0
17    while  BOUND(cp，cw，k，W)  ≤  fp  do
18       while k≠0 and Y(k)≠1 do
19            (3)
20       if k=0 then return
21       Y[k]←0
22       cw←cw-w[k]
23       cp←cp-v[k]
24      (4)
【問題2】考慮下表所示的實例，假設(shè)有3個物品，背包容量為22。



下圖是根據(jù)上述算法構(gòu)造的搜索樹，其中結(jié)點的編號表示了搜索樹生成的順序，邊上的數(shù)字1/0分別表示選擇/不選擇對應(yīng)物品。除了根結(jié)點之外，每個左孩子結(jié)點旁邊的上下兩個數(shù)字分別表示當前背包的重量和已獲得的價值，右孩子結(jié)點旁邊的數(shù)字表示擴展了該結(jié)點后最多可能獲得的價值。為獲得最優(yōu)解，應(yīng)該選擇物品  (5)  ，獲得的價值為  (6)  。

對于上述實例，若采用窮舉法搜索整個解空間，則搜索樹的結(jié)點數(shù)為  (7)  ，而用了上述回溯法，搜索樹的結(jié)點數(shù)為  (8)  。