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

作者：IT小白 | 2024-03-29 01:55:40

踩

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)

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

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

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

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

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/332996

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