#title P11: 背包問題的搜索解法《背包問題九講》的本意是將背包問題作為動態(tài)規(guī)劃問題中的一類進行講解。但鑒于的確有一些背包問題只能用搜索來解，所以這里也對用搜索解背包問題做簡單介紹。大部分以01背包為例，其它的應(yīng)該可以觸類旁通。* 簡單的深搜對于01背包問題，簡單的深搜的復(fù)雜度是O(2^N)。就是枚舉出所有2^N種將物品放入背包的方案，然后找最優(yōu)解。基本框架如下：<src>procedure SearchPack(i,cur_v,cur_w)    if(i>N)        if(cur_w>best)            best=cur_w        return    if(cur_v+v[i]<=V)        SearchPack(i+1,cur_v+v[i],cur_w+w[i])    SearchPack(i+1,cur_v,cur_w)</src>其中cur_v和cur_w表示當前解的費用和權(quán)值。主程序中調(diào)用SearchPack(1,0,0)即可。* 搜索的剪枝基本的剪枝方法不外乎可行性剪枝或最優(yōu)性剪枝。可行性剪枝即判斷按照當前的搜索路徑搜下去能否找到一個可行解，例如：若將剩下所有物品都放入背包仍然無法將背包充滿（設(shè)題目要求必須將背包充滿），則剪枝。最優(yōu)性剪枝即判斷按照當前的搜索路徑搜下去能否找到一個最優(yōu)解，例如：若加上剩下所有物品的權(quán)值也無法得到比當前得到的最優(yōu)解更優(yōu)的解，則剪枝。* 搜索的順序在搜索中，可以認為順序靠前的物品會被優(yōu)先考慮。所以利用貪心的思想，將更有可能出現(xiàn)在結(jié)果中的物品的順序提前，可以較快地得出貪心地較優(yōu)解，更有利于最優(yōu)性剪枝。所以，可以考慮將按照“性價比”（權(quán)值/費用）來排列搜索順序。另一方面，若將費用較大的物品排列在前面，可以較快地填滿背包，有利于可行性剪枝。最后一種可以考慮的方案是：在開始搜索前將輸入文件中給定的物品的順序隨機打亂。這樣可以避免命題人故意設(shè)置的陷阱。以上三種決定搜索順序的方法很難說哪種更好，事實上每種方法都有適用的題目和數(shù)據(jù)，也有可能將它們在某種程度上混合使用。* 子集和問題子集和問題是一個NP-Complete問題，與前述的（加權(quán)的）01背包問題并不相同。給定一個整數(shù)的集合S和一個整數(shù)X，問是否存在S的一個子集滿足其中所有元素的和為X。這個問題有一個時間復(fù)雜度為O(2^(N/2))的較高效的搜索算法，其中N是集合S的大小。第一步思想是二分。將集合S劃分成兩個子集S1和S2，它們的大小都是N/2。對于S1和S2，分別枚舉出它們所有的2^(N/2)個子集和，保存到某種支持查找的數(shù)據(jù)結(jié)構(gòu)中，例如hash set。然后就要將兩部分結(jié)果合并，尋找是否有和為X的S的子集。事實上，對于S1的某個和為X1的子集，只需尋找S2是否有和為X-X1的子集。假設(shè)采用的hash set是理想的，每次查找和插入都僅花費O(1)的時間。兩步的時間復(fù)雜度顯然都是O(2^(N/2))。實踐中，往往可以先將第一步得到的兩組子集和分別排序，然后再用兩個指針掃描的方法查找是否有滿足要求的子集和。這樣的實現(xiàn)，在可接受的時間內(nèi)可以解決的最大規(guī)模約為N=42。* 搜索還是DP?在看到一道背包問題時，應(yīng)該用搜索還是動態(tài)規(guī)劃呢？首先，可以從數(shù)據(jù)范圍中得到命題人意圖的線索。如果一個背包問題可以用DP解，V一定不能很大，否則O(VN)的算法無法承受，而一般的搜索解法都是僅與N有關(guān)，與V無關(guān)的。所以，V很大時（例如上百萬），命題人的意圖就應(yīng)該是考察搜索。另一方面，N較大時（例如上百），命題人的意圖就很有可能是考察動態(tài)規(guī)劃了。另外，當想不出合適的動態(tài)規(guī)劃算法時，就只能用搜索了。例如看到一個從未見過的背包中物品的限制條件，無法想出DP的方程，只好寫搜索以謀求一定的分數(shù)了。[[Index][首頁]]--------Copyright (c)  2007  Tianyi CuiPermission is granted to copy, distribute and/or modify this document under the terms of the [[http://www.gnu.org/licenses/fdl.txt][GNU Free Documentation License]], Version 1.2 or any later version published by the Free Software Foundation.