伪代码用回溯法求解0-1背包问题及该问题的时间复杂度

以下是0-1背包问题的回溯法伪代码：

function backtrack(i, cur_weight, cur_value)
    if cur_weight > W or i == n+1:    // 背包已经装满或者物品已经都考虑完毕
        return cur_value             // 返回当前价值
    else:
        // 选择不装第i个物品
        backtrack(i+1, cur_weight, cur_value)
        // 选择装第i个物品
        backtrack(i+1, cur_weight + w[i], cur_value + v[i])

max_value = backtrack(1, 0, 0)   // 从第一个物品开始考虑，背包重量为0，价值为0

时间复杂度：$O(2^n)$，因为每个物品都有两种选择，所以回溯树的节点数是$2^n$。但是由于剪枝等优化策略的使用，实际运行时间通常会远远小于$2^n$。