0-1背包问题的多种解法

速度慢 改进剪枝Р 分枝限界法 O(n2n )Р 最优解 速度慢 优化限界函数Р 从计算复杂性理论看，背包问题是 NP 完全问题。半个多世纪以来，该问题一直是算法Р 与复杂性研究的热门话题。通过对 0-1 背包问题的算法研究可以看出，回溯法和分枝限界Р 法等可以得到问题的最优解，可是计算时间太慢；动态规划法也可以得到最优解，当 m 2nР 时，算法需要O(n2n )Р 的计算时间，这与回溯法存在一样的缺点——计算速度慢；采用贪心Р 算法，虽然耗费上优于前者，但是不一定是最优解。目前，以上几种方法中回溯法、动态规Р 划法、贪心法都广泛地应用到不同的实际问题中，并在应用中不断地改进。