【01背包问题】：动态规划、回溯法和分支限界法三种算法的对比与分析（时间复杂度方面）

01背包问题的动态规划解法递归方程为：

当 j >= wi 时, m(i, j) = max { m(i-1, j), m(i-1, j-wi) + vi }; 
当 j < wi 时， m(i, j) = m(i-1, j)

1 2	当 j >= wi 时, m(i, j) = max { m(i-1, j), m(i-1, j-wi) + vi }; 当 j < wi 时， m(i, j) = m(i-1, j)

此时时间复杂度为O(n)。

使用回溯法解决01背包问题时，若可选物品为n个，则其解空间由长度为n的0-1向量组成。

此时时间复杂度为O(n2^n)。

使用分支限界法时，首先要对数据进行预处理，将物品重量价值按从小到大排列。分治限界法的缺点是占用内存大，效率不高。

时间复杂度为O(2^n)。