Question

关于01背包问题

一般用动态规划做,但是我的动态规划不好,就用回溯做.我想知道用回溯的话复杂度会大多少?用时会比动态规划多多少?

Answer 1

实在是佩服，精神可嘉，但我还是建议你把dp学会。不会dp的话实在是寸步难行啊！
dp的复杂度为O(n)
穷举的复杂度为O(2^n)
回溯的时间复杂度介于两者之间，但还是非常大的。对于大规模的数据肯定会爆。好自为之吧！

Answer 2

01背包问题是动态规划中最最基础的，楼主一定要掌握好啊。
回溯的复杂度是（2^n)
完全不能和dp比较啊

Answer 3

动态规