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

动态规划(dp)

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

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

回溯法

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

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

分支限界法

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

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