p11.muse

经典的背包问题九讲

#title P11: 背包问题的搜索解法

《背包问题九讲》的本意是将背包问题作为动态规划问题中的一类进行讲解。但鉴于的确有一些背包问题只能用搜索来解，所以这里也对用搜索解背包问题做简单介绍。大部分以01背包为例，其它的应该可以触类旁通。

* 简单的深搜

对于01背包问题，简单的深搜的复杂度是O(2^N)。就是枚举出所有2^N种将物品放入背包的方案，然后找最优解。基本框架如下：

<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表示当前解的费用和权值。主程序中调用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的方程，只好写搜索以谋求一定的分数了。

[[Index][首页]]

--------

Copyright (c)  2007  Tianyi Cui

Permission 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.