背包问题的搜索解法

(1) 代码

对于0/1背包问题，简单的深搜的复杂度是O(2n)。就是枚举出所有2n 种将物品放入背包的方案，然后找最优解。代码如下（调用try(1,0,0)即可）：

int max=0; void try(int i, int curw, int curv) // i是当前物体，curw是当前重量，curv是当前的价值 {  if (i>n)

{   if (curv > max) max = curv;   return; }   if (curw + w <= C) try(i+1, curw + w, curv + v);  try(i+1, curw, curv); }

(2) 预处理和剪枝

预处理：在搜索中，可以认为顺序靠前的物品会被优先考虑。

所以，可以利用贪心的思想，将更有可能出现在结果中的物品的顺序提前，可以较快地得出贪心的较优解，也更有利于最优性剪枝。这需要按照“性价比”（权值/费用）来排列搜索顺序。

另一方面，若将费用较大的物品排列在前面，可以较快地填满背包，有利于可行性剪枝。

最后一种可以考虑的方案是：在开始搜索前将给定的物品的顺序打乱。这样可以避免命题人设置的陷阱。

可行性剪枝：即判断按照当前的搜索路径搜下去能否找到一个可行解，例如：若将剩下所有物品都放入背包仍然无法将背包充满（设题目要求必须将背包充满），则剪枝。

最优性剪枝：即判断按照当前的搜索路径搜下去能否找到一个最优解，例如：若加上剩下所有物品的权值也无法得到比当前得到的最优解更优的解，则剪枝。

(3) 搜索还是DP

在看到一道背包问题时，应该用搜索还是动态规划呢？

如果一个背包问题可以用动态规划求解，V 一定不能很大，否则O(VN)的算法无法承受，而一般的搜索解法都是仅与 N 有关，与 V 无关。

所以，V 很大时，应该优先考虑搜索；N 较大时，应该优先考虑动态规划。

另外，当想不出合适的动态规划算法时，就只能用搜索了。