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